Иерархия Хомского. Регулярные языки.

   Классификация грамматик по сложности  соответствующих  прог-
рамм-распознавателей называется иерархией Хомского. В ней выде-
лены 4 класса грамматик (в порядке возрастания сложности):
    а) регулярные (или автоматные). Правила имеют вид:
           A : xB или A : x, где x - цепочка терминалов или e
           Примеры - упражнение.
    б) контекстно-свободные (или КС). Правила имеют вид:
           A : y, где y - цепочка из терминалов и нетерминалов
           Примеры - "скобочный  язык"  из  предыдущей  лекции,
           язык арифметических формул
    в) контекстно-зависимые  (неукорачивающие).  Правила  имеют
       вид :
           z : y, где z и y - цепочки из терминалов и  нетерми-
           налов, z содержит нетерминал, |z| <= |y|
                    n n n
           Пример: a b c
    г) без ограничений

   Класс языка определяется классом  самой  простой  (в  смысле
иерархии Хомского) из описывающих его грамматик. Следующие вло-
жения  для  классов  языков  очевидны,  если  не  рассматривать
КС-грамматики, содержащие так называемые e-правила - правила  с
пустой правой частью. (Упражнение: показать, что любой  КС-язык
может быть описан грамматикой без e-правил).

 а < б < в < рекурсивные множества < г = рек.перечислимые мн-ва

   Для языка, определенного регулярной грамматикой, всегда мож-
но написать контекстно-свободную грамматику (и даже  грамматику
без ограничений!). Тем не менее, все вложения строгие: в каждом
классе существуют языки, которые нельзя задать грамматиками бо-
лее простого класса.

                       Конечные автоматы

   Рассмотрим другой способ задания регулярных  языков.  (Неде-
терминированный) конечный автомат задается:
 - алфавитом входных символов E;
 - множеством состояний S;
 - тернарным отношением переходов на множестве { S, E U e, S };
 - начальным состоянием - выделенным состоянием в S, и
 - конечными состояниями - непустым подмножеством S.
Принято изображать автомат в виде ориентированного графа,  узлы
которого соответствуют состояниям (конечные состояния мы  будем
заключать в двойную рамку), а ребра, помеченные символами вход-
ного алфавита или е, изображают отношение переходов.
   Цепочка допускается автоматом если и только если  существует
пусть из начального в одно из конечных  состояний,  такой  что,
прочитав метки ребер вдоль этого пути, мы получим исходную  це-
почку (буква e, естественно, не читается). Например, автомат

            --------¬  0  --------¬  1  -T-----T¬
            ¦   S   +-->--+   B   +-->--+¦  C  ¦¦
            L--------     L---T----     L+--T--+-
                              L------<-------0

допускает цепочки (01)+. Этот  язык  можно  описать  регулярной
грамматикой:

        S : 0 B     B : 1 C     C : 0 B     C : e

   Несложно показать (упражнение),  что  для  каждого  автомата
можно построить регулярную грамматику, описывающую тот же самый
язык, и наоборот.

   Детерминированный конечный автомат -  частный  случай  неде-
терминированного, в котором:
 - нет e-переходов,
 - отношение переходов является однозначной функцией 

         f:( S x E U e ) -> S,

определенной, может быть, не для всех пар из SxEUe. В  терминах
графа это означает, что из одного состояния  выходит  не  более
одного ребра с одинаковой меткой.

   Для детерминированного автомата очень просто проверять  при-
надлежность цепочки из E* языку. Добавив, если нужно, еще  одно
"тупиковое" состояние, можно сделать функцию переходов  опреде-
ленной на всех парах из S x E.

    ----T------¬
    ¦   ¦ 0  1 ¦   s := начальное состояние
    +---+------+   цикл для каждого символа цепочки c выполнить
    ¦ S ¦ B  F ¦   . s := f( s, c )
    ¦ B ¦ F  C ¦   конец цикла
    ¦ C ¦ B  F ¦   ответ := s - конечное состояние
    ¦ F ¦ F  F ¦
    L---+-------

   Такая интерпретация  детерминированного  конечного  автомата
более наглядна и общепринята: KA -  устройство,  которое  может
находится в конечном множестве состояний и переходит из  одного
состояния в другоe под действием внешних событий из алфавита E.
   Можно ли подобным образом интерпретировать недетерминирован-
ный автомат (или хотя бы эффективно  определять  принадлежность
цепочки языку)? Да, можно считать, что в том случае, когда воз-
можен более чем один переход, создается необходимое  число  эк-
земпляров КА, которые переводятся во все возможные в этой ситу-
ации состояния. Цепочка считается допущенной, если хотя бы один
из экземпляров оказался в конечном состоянии.

               -<--------------------------¬0
           ----+---¬  0  --------¬  1  -T--+--T¬
           ¦   S   +-->--+   B   +-->--+¦  C  ¦¦
           L--------     L---T----     L+--T--+-
                             L<-------------0

Какие цепочки допускает этот автомат? - упражнение.
   Заметим, что если несколько экземпляров недетерминированного
КА оказались в одном состоянии, то в дальнейшем можно  рассмат-
ривать только один из них. Таким  образом,  максимальное  коли-
чество экземпляров не превосходит числа состояний.
   Проверить, допускает ли недетерминированный конечный автомат
цепочку символов, также несложно:

        S := e-замыкание( { начальное состояние } )
        цикл для каждого символа цепочки c выполнить
        . S := e-замыкание( F( S, c ) )
        конец цикла
        ответ := ( S П конечные состояния ) - непусто

Здесь:  S                - подмножество множества состояний KA;
        e-замыкание( S ) - множество состояний, достижимых из S
                           за 0 и более e-переходов;
        F( S, c )        - множество состояний, достижимых из S
                        за один переход, помеченный символом c.

   Упражнение по программированию: придумайте структуры  данных
для представления детерминированного и недетерминированного ко-
нечных автоматов и запрограммируйте проверку допуска строки  из
символов ASCII KA. Это можно (и следует) делать за время
- O(длина цепочки)                  для детерминированного и
- O(длина цепочки*число состояний) для недетерминированного КА.


  Преобразование недетерминированного КА в детерминированный

   Недетерминированный КА всегда можно преобразовать в  эквива-
лентный (т.е. допускающий то же множество цепочек) детерминиро-
ванный КА. Рассмотрим новый КА, состояниями которого будут под-
множества множества состояний исходного КА (если исходный авто-
мат имел m состояний, сколько их будет у нового? - упражнение).
Исходным для нового автомата будет состояние {Начало}, конечны-
ми - все состояния, содержащие исходное конечное состояние. Пе-
реход A -> B по символу d имеется  в  новом  автомате  тогда  и
только тогда, когда в исходном автомате для любого состояния  b
из B, существует a из A такое, что по символу d возможен  пере-
ход a -> b, и других переходов по d из A нет. Новый автомат бу-
дет детерминированным и эквивалентным исходному.
    Действительно, состояние нового автомата a+b  соответствуют
размещению экземпляров исходного недетерминированного КА в сос-
тояниях a и b, а переход в новом автомате соответствует перехо-
дам всех экземпляров недетерминированного КА.
   Для практических целей применяется аналогичный алгоритм: На-
зовем состояния неразличимыми, если в них происходит переход из
одного и того же состояния при одном и том же входном  символе.
Возьмем любое множество неразличимых состояний и добавим в спи-
сок состояний КА еще одно - их "сумму", перемещая переходы:

       Было:                 ¦           Стало:
--¬1 --¬0 --¬                ¦  --¬1 ----¬0
¦ +->+Б+->+В¦                ¦  ¦ +->+Б+Г+>T->¬
¦А¦  L--  L--                ¦  ¦А¦  L---- ¦  ¦
¦ ¦1 --¬0 --¬                ¦  ¦ ¦  --¬0 -+¬ ¦
¦ +->+Г+->+Д¦                ¦  ¦ ¦  ¦Б+->+В¦ ¦
L--  LT-  L--                ¦  L--  L--  L-- ¦
--¬1  ¦                      ¦  --¬1 --¬0    -+¬
¦Е+->--                      ¦  ¦Е+->+Г+->---+Д¦
L--                          ¦  L--  L--     L--

Получим новый (быть может, вновь недетерминированный) КА. Будем
повторять наши действия, пока в КА остаются неразличимые состо-
яния. Этот процесс в конце концов завершится (почему? -  упраж-
нение). При этом мы получим детерминированный автомат,  эквива-
лентный исходному (почему? - упражнение).
   Применив этот метод к недетерминированному КА из  примера  в
этой лекции, получим:
                                     --<----------¬ 1
       --------¬ 0  --------¬ 1  -T--+--T¬0  -----+----¬
       ¦   S   +->--+   B   +->--+¦  C  ¦+-->+  S + B  ¦
       L--------    L---T----    L+-----+-   L----T-----
                        L--<----------------------- 0

                 Минимизация конечного автомата

   По конечному автомату часто можно построить автомат с  мень-
шим числом состояний, эквивалентный исходному.  Соответствующий
процесс называется  минимизацией  конечного  автомата.  Вначале
выбросим из автомата все состояния, недостижимые из начального.
Затем разобьем все состояния КА на классы эквивалентности  сле-
дующим способом: в первый класс отнесем все конечные состояния,
а во второй - все остальные. Назовем  эти  состояния  0-эквива-
лентными. Теперь построим новое 1-эквивалентное разбиение,  вы-
делив те состояния, которые по одинаковым символам переходят  в
0-эквивалентные состояния.  Последовательно  строя  n+1-эквива-
лентные состояния по n-эквивалентным, мы будем увеличивать чис-
ло классов эквивалентности. Прекратим этот процесс тогда, когда
n+1-эквивалентное состояние совпадет с n-эквивалентным.  Каждый
полученный класс эквивалентности и будет состоянием нового  ми-
нимизированного КА, эквивалентного исходному (почему? -  упраж-
нение).
   Рассмотрим, например, следующий КА:

                --------¬1   -T-----T¬ 0--------¬
     -------¬0->+   B   +->--+¦  D  ¦+<-+   F   ¦
     ¦Начало+-- L-T------   -++---T-+-  L---T-T--
     ¦      ¦     ¦  --<-----0 -->- ¦1   -->- ¦1
     ¦      ¦     ¦  ¦         ¦    ¦    ¦    ¦
     ¦      ¦     L<-+------¬0 ¦1 -<-    ¦0 -<-
     ¦  A   +-¬ -----+--¬1  LTT+--+-T¬ 1-+--+---¬
     L-------1L>+   C   +->--+¦  E  ¦¦<-+   G   ¦
                L--------    L+-----+-  L--------

Состояния F и G недостижимы (это можно выяснить, например,  вы-
числив транзитивное замыкание отношения "есть  переход").  Пос-
троим классы n-эквивалентности для оставшихся состояний:
       n        Классы
       0      (ABC) (DE)
       1      (A) (BC) (DE)
       2      (A) (BC) (DE)
Результат:

            ------¬0,1  ------¬1    -T---T¬
            ¦  A  +---->+ B+C +---->+¦D+E¦¦
            L------     L--T---     L+-T-+-
                           L-<----------0

   Упражнение:  докажите,  что  для  любого  КА  существует   и
единственен с  точностью  до  изоморфизма  минимальный  эквива-
лентный ему конечный автомат. Покажите, что описанный выше  ал-
горитм минимизации получает на выходе минимальный автомат.
   Упражнение по программированию: придумайте структуры  данных
и запрограммируйте процедуры построения детерминированного КА,
и минимизации КА. Какая временная и пространственная  сложность
предложенных вами алгоритмов в терминах числа состояний  исход-
ного и выходного автоматов?


            Регулярные языки и регулярные выражения

   Рассмотрим специальный класс операций над языками - регуляр-
ные операции, множество языков, получаемое в результате  приме-
нения конечного числа регулярных операций из элементарных  язы-
ков, - регулярные множества, способ их  описания  -  регулярные
выражения и недетерминированные конечные автоматы,  допускающие
цепочки из этих множеств.

---------------------T-----------T----------------------------¬
¦    Регулярное      ¦Регулярное ¦    Конечный автомат        ¦
¦     множество      ¦ выражение ¦                            ¦
+--------------------+-----------+----------------------------+
¦  Пустая цепочка    ¦     e     ¦   ------¬   e   -T---T¬    ¦
¦                    ¦           ¦   ¦  S  +--->---+¦ E ¦¦    ¦
¦                    ¦           ¦   L------       L+---+-    ¦
+--------------------+-----------+----------------------------+
¦ Один символ a из E ¦     a     ¦   ------¬   а   -T---T¬    ¦
¦                    ¦           ¦   ¦  S  +--->---+¦ E ¦¦    ¦
¦                    ¦           ¦   L------       L+---+-    ¦
+--------------------+-----------+----------------------------+
¦                    ¦           ¦ ----¬ e --T-----T-¬ e -T-T¬¦
¦  P U Q             ¦    p|q    ¦ ¦   +->-+s¦Авт.P¦e+->-+¦ ¦¦¦
¦                    ¦           ¦ ¦ S ¦   L-+-----+--   ¦¦E¦¦¦
¦                    ¦           ¦ ¦   ¦ e --T-----T-¬ e ¦¦ ¦¦¦
¦                    ¦           ¦ ¦   +->-+s¦Авт.Q¦e+->-+¦ ¦¦¦
¦                    ¦           ¦ L----   L-+-----+--   L+-+-¦
+--------------------+-----------+----------------------------+
¦  PQ (конкатенация) ¦    pq     ¦ ----T-----T----T-----TT-T¬ ¦
¦                    ¦           ¦ ¦ S ¦Авт.P¦ es ¦Авт.Q¦¦Е¦¦ ¦
¦                    ¦           ¦ L---+-----+----+-----++-+- ¦
+--------------------+-----------+----------------------------+
¦  P* (итерация)     ¦    p*     ¦          ---<----¬e        ¦
¦                    ¦           ¦ ----¬ e -+T-----T+¬ e -T-T¬¦
¦                    ¦           ¦ ¦ S +->-+s¦Авт.P¦e+->-+¦E¦¦¦
¦                    ¦           ¦ L-T--   L-+-----+--   L+T+-¦
¦                    ¦           ¦  eL---------->-----------  ¦
+--------------------+-----------+----------------------------+
¦   P (просто скобки)¦    (p)    ¦    ------T-------TT---T¬   ¦
¦                    ¦           ¦    ¦  S  ¦ Авт.P ¦¦ E ¦¦   ¦
¦                    ¦           ¦    L-----+-------++---+-   ¦
L--------------------+-----------+-----------------------------

   В регулярном выражении "*" имеет больший приоритет, чем кон-
катенация, а конкатенация - больший чем "|". Примеры регулярных
выражений: (0|1)*, (0|1)(0|1)*. Какие множества они описывают?
   Для регулярного выражения предложен способ построения  неде-
терминированного конечного автомата, допускающего  соответству-
ющее выражению регулярное множество.  Предложенная  конструкция
не является самой  экономной  (автомат  обычно  содержит  много
"лишних"  e-переходов),  однако  построенный  автомат  обладает
следующими полезными свойствами:
 - у него только одно конечное состояние,
 - в начальное состояние не входит ни одно ребро,
 - из конечного состояния не выходит ни одно ребро.
   Таким образом, мы доказали, что регулярные множества < регу-
лярные языки = языки, допускаемые КА. Покажем, что  допускаемое
КА множество - регулярно. (Это утверждение называется  теоремой
Клини).
   Доказательство: Пусть S1,...Sn - состояния детерминированно-
го КА, S1 - начальное состояние. Рассмотрим все  пути  в  графе
переходов с началов в Si, концом в Sj, промежуточными узлами из
множества {S1...Sk} (1<=i<=n, 1<=j<=n, 0<=k<=n) и множества це-
почек из E - L(i,j,k), соответствующие этим путям. Докажем  ин-
дукцией по k, что множества L - регулярны.
   L(i,j,0) - состоит из меток ребер, ведущих из Si в Sj,  сле-
              довательно, регулярно.
Для 0<=k<=n-1
   L(i,j,k+1) = L(i,j,k) U  L(i,k+1,k) L(k+1,k+1,k)* L(k+1,j,k)
   получено с помощью регулярных операций  из  регулярных  мно-
   жеств, следовательно, регулярно.

Множество цепочек, допускаемых КА, представляет  собой  объеди-
нение цепочек L(1,j,n), таких, что Sj - конечное состояние  КА,
следовательно, регулярно. (Конец доказательства).

   Мы рассмотрели 4 способа описания языков:
 - регулярные (автоматные, праволинейные) грамматики,
 - недетерминированные КА,
 - детерминированные КА,
 - регулярные выражения,
и показали, что они описывают один класс  языков  -  регулярные
языки. Этот класс языков "устроен очень хорошо" - для всех  ти-
пичных вопросов известны ответы и эффективные алгоритмы. Приме-
ры таких вопросов (получение ответов - упражнение):
 - является ли объединение, пересечение, дополнение  регулярных
   языков регулярным,
 - является ли регулярный язык конечным, пустым,
 - совпадают ли два регулярных языка,
 - является ли один регулярный язык подмножеством другого,
   и т.д.

(Замечание. Для других классов иерархии Хомского  дела  обстоят
значительно  хуже,  например,  проблема   эквивалентности   для
КС-языков алгоритмически неразрешима.)

           Лемма о разрастании для регулярных языков

   Так называмые "леммы о разрастании"  для  классов  языков  -
удобный способ доказательства того, что конкретный язык не  от-
носится к данному классу.
   Лемма для регулярного языка: Существует такое число  m,  что
любую цепочку x, |x| > m, принадлежащую языку, можно разбить на
три части: x = uvw так, что 0<|v|<=m и цепочки uv*w также будут
принадлежать языку. Доказательство: построим КА для распознава-
ния языка. Пусть этот автомат имеет m состояний. Тогда при раз-
боре цепочки x хотя бы одно из состояний (например,  А)  прохо-
дится дважды (почему? - упражнение). Разобьем цепочку x на  три
части - до состояния А, от А до А, остальное. Это и есть цепоч-
ки u,v,w (почему v можно  размножать,  сохраняя  принадлежность
цепочки языку? - упражнение).
                           n n
   Как показать, что язык 0 1 не является регулярным? -  упраж-
нение.

                     Задачи и упражнения

   1. Написать регулярную грамматику  и  регулярное  выражение,
порождающие тот же язык, что и грамматика:
   S : AB ;   A : X|Y ;   X : x|xX ;   Y : y|yY ;   B : b|bB

   2. Построить регулярную грамматику и конечный автомат, соот-
ветствующие регулярному выражению:

        (101)*(010)*

   3. Постройте недетерминированный а  затем  детерминированный
конечные автоматы, воспринимающие регулярное выражение:

        (101)*(110)*

   4. Построить детерминированные конечные автоматы для  следу-
ющих регулярных выражений.  Для  каждого  полученного  автомата
построить эквивалентный минимальный автомат. Убедиться  в  изо-
морфизме минимальных автоматов, следовательно, в эквивалентнос-
ти исходных выражений:
   (a|b)*   (a*|b*)*   ((e|a)b*)*

   5. Написать регулярное выражение, описывающее следующий язык
 - слово, буквы которого расположены в алфавитном порядке
 - последовательность цифр, в которой нет повторяющихся цифр
 - последовательность цифр, в которой не более чем  одна  цифра
   встречается несколько раз
 - строка из нулей и единиц, в которой нет подстроки 0 0 1
 - строка из нулей и единиц, в  которой  нет  подпоследователь-
   ности 0 0 1

   6. Опишите регулярной грамматикой и приведите регулярное вы-
ражение для идентификатора Фортрана. (До шести букв  или  цифр,
первый символ должен быть буквой).

   7. Напишите программу распознавания  вещественных  констант.
Она должна воспринимать константы вида:

1.2  -0.4 +3.14 .2 1. -1.е38 1е+2 +0.5е-23 и т.д.

   8. Построить минимальные детерминированные конечные автоматы
для следующих регулярных выражений
   (a|b)*a(a|b)
   (a|b)*a(a|b)(a|b)
   (a|b)*a(a|b)(a|b)(a|b)
Доказать, что любой детерминированный конечный автомат для  вы-
ражения (a|b)a(a|b)(a|b)...(a|b), содержащего n-1 (a|b) в конце
содержит не менее чем 2**n состояний.

   9. Напишите программу, которая проверяет,  является  ли  имя
файла частным случаем разновидности  регулярного  выражения,  в
котором метасимвол * обозначает любую (в том  числе  и  пустую)
последовательность символов кроме ".", а метасимвол ?  -  любой
символ кроме "."