Регулярные выражения и языки (стр. 3 )

Теорема 3.4. Если L = L(A) для некоторого ДКА А, то существует регулярное выра­жение R, причем L = L(R).

Доказательство. Предположим, что {1,2, ..., п) — множество состояний автомата А для некоторого натурального п. Независимо от того, какими эти состояния являются на самом деле, их конечное число п, поэтому их можно переименовать, используя первые п положительных целых чисел. Нашей первой и наиболее сложной задачей является по­строение набора регулярных выражений, которые описывают постепенно расширяю­щиеся множества путей в диаграмме переходов автомата Л.

Обозначим через R. p регулярное выражение, язык которого состоит из множества меток w путей, ведущих от состояния i к состоянию j автомата А и не имеющих проме­жуточных состояний с номерами больше к. Заметим, что начальная и конечная точки пу­ти не являются "промежуточными", поэтому мы не требуем, чтобы i и/или j были мень­ше или равны к.

Условия, налагаемые на пути выражениями, представлены на рис. 3.2. Здесь на вертикальной оси расположены состояния, начиная с 1 внизу до п вверху, а горизонталь­ная ось представляет движение вдоль пути. Заметим, что на этой диаграмме показан слу­чай, когда i и j больше, чем к, но любое из этих чисел, или оба, могут быть меньше или равны к. Также обратите внимание на то, что путь дважды проходит через вершину к, но только в крайних точках поднимается выше, чем к.

Рис. 3.2. Путь, отметка которого принадлежит языку регулярного выражения

Для построения выражения R-р используют следующее индуктивное определение, которое начинается с к = 0 и достигает к = п. Заметим, что при к = п пути ничем не огра­ничиваются, поскольку нет состояний с номерами, которые больше, чем п.

Базис. В качестве базиса примем к = 0. Поскольку все состояния пронумерованы от 1 и далее, то это условие означает, что у пути вообще нет промежуточных состояний. Су­ществует только два вида путей, удовлетворяющих такому условию.

Дуга, ведущая от вершины (состояния) i к вершине j. Путь длины 0, состоящий лишь из некоторой вершины /.

Если i Ф j, то возможен только первый случай. Необходимо проанализировать данный ДКА А и найти такие входные символы а, по которым есть переход из состояния i в со­стояние j:

а) если таких символов нет, то Л^0' =0;

б)        если существует только один такой символ а, то = а;

в)        если существуют такие символы аь а2, ..., ак, которыми помечены дуги из состояния i в состояние j, то = а, + а2 + ... + ак.

В то же время, если i =j, то допустимыми путями являются путь длины 0 и все петли, которые начинаются и заканчиваются в состоянии Л Путь длины 0 может быть представ­лен регулярным выражением Ј, потому что вдоль этого пути нет символов. Следователь­но, добавляем е к выражениям, полученным выше в пунктах (а)—(в). Таким образом, в случае (а) [нет ни одного символа a] получим выражение Ј, в случае (б) [один символ а] выражение примет вид е + а, и в случае (в) [несколько символов] получим выражение Ј+ + а2 + ... + ак.

Индукция. Предположим, что существует путь из состояния i в состояние j, не про­ходящий через состояния с номерами, которые больше, чем к. Необходимо рассмотреть две ситуации.

Путь вообще не проходит через состояние к. В этом случае метка пути принадлежит языку Rf~X).

Путь проходит через состояние к по меньшей мере один раз. Тогда мы можем разде­лить путь на несколько частей, как показано на рис. 3.3. Первая часть ведет от со­стояния / к состоянию к, но не проходит через к, последняя ведет из А: в j, также не проходя через к, а все части, расположенные внутри пути, ведут из к в к, не проходя через к. Заметим, что если путь проходит через состояние к только один раз, то "внутренних" частей нет, а есть только путь из / в к и путь из А: в j. Множество меток для всех путей такого вида может быть представлено регулярным выражением К-л Ч) (^li" )* • Таким образом, первое выражение представляет часть пути, ве­дущую в состояние к в первый раз, второе — часть, ведущую т кв к нуль или не­сколько раз, и третье выражение— часть пути, которая выходит из состояния к в последний раз и ведет в состояние j.

Нуль или несколько цепочек в

Рис. 3.3. Путь из i в j может быть разбит на несколько сегментов в каждой точке, в которой он проходит через состояние к

После объединения выражений для путей двух рассмотренных выше типов получим следующее выражение для меток всех путей, ведущих из состояния / в состояние j, кото­рые не проходят через состояния с номерами, которые больше, чем к.

/#> = + дГЧдГ'ГдГ"

Поскольку данные выражения строятся в порядке возрастания верхнего индекса, можно построить любое выражение R(,p, так как оно зависит только от выражений с меньшими значениями верхнего индекса.

В итоге получим R\"] для всех i и j. Можно предположить, что состояние 1 является на­чальным, а множество допускающих (заключительных) состояний может быть любым. То­гда регулярным выражением для языка, допускаемого данным автоматом, будет сумма (объединение) всех тех выражений R\"?, в которых состояние j является допускающим. □

Пример 3.5. Преобразуем ДКА, представленный на рис. 3.4, в соответствующее ре­гулярное выражение. Этот ДКА допускает все цепочки, содержащие хотя бы один 0. Чтобы понять, почему это так, заметим, что автомат переходит из начального состояния 1 в заключительное состояние 2, как только на входе появляется 0. Далее автомат остает­ся в заключительном состоянии 2 при любой входной последовательности.

1

Начало        0

Рис. 3.4. ДКА, допускающий все цепочки, которые содержат хотя бы один О Ниже приведены базисные выражения для построений согласно теореме 3.4.

<>	Ј + 1
0
Ы0) 21	0
0(0) 22	(Ј+0 + 1)

Например, в выражении присутствует член е, потому что и начальным, и конеч­ным является состояние 1. Это выражение включает также 1, поскольку существует путь из состояния 1 в состояние 1 по входу 1. Выражение R^ равно 0, потому что есть дуга с меткой 0, ведущая из состояния 1 в состояние 2. Здесь нет члена Ј, поскольку начальное и конечное состояния различаются. И, наконец, R^ = 0, так как нет путей, ведущих из состояния 2 в состояние 1.

Теперь применим индукцию для построения более сложных выражений. Вначале они соответствуют путям, проходящим через состояние 1, а затем путям, которые могут про­ходить через состояния 1 и 2, т. е. любым путям. Правило для вычисления выражения р^Р представляет собой пример общего правила из индуктивной части теоремы 3.4.

4° = + ^(/ОЧ?        (ЗЛ)

В таблице на рис. 3.5 сначала представлены выражения, полученные с помощью пря­мой подстановки в приведенную выше формулу, а затем упрощенные выражения, кото­рые определяют те же языки, что и более сложные выражения.

Прямая подстановка	Упрощенное выражение
D( О П11	Ј+ 1 + (Ј+ 1)(Ј+ 1)*(Ј+ 1)	1*
Rd) 12	0 + (Ј+ 1)(Ј+ 1)*0	1*0
D(l) 21	0 + 0(Ј+1)*(Ј+1)	0
D( 1) 22	Ј+0 + 1 +0(Ј+ 1)*0	Ј+0+1

Рис. 3.5. Регулярные выражения для путей, которые могут проходить только через состояние 1

Например, рассмотрим выражение Rff. Подставив /= 1 и у = 2 в (3.1), получим

Общим принципом упрощения является следующий: если R— произвольное регу­лярное выражение, то (е + R)* = R*. Он основан на том, что обе части этого равенства описывают язык, образованный конкатенациями нуля или нескольких цепочек из L(R). В нашем случае (Ј + 1)* = 1*; отметим, что оба выражения описывают цепочки, состоящие из любого количества единиц. Далее, (Ј + 1)1* = 1*. Опять-таки, легко заметить, что оба выражения означают "любое количество единиц". Следовательно, исходное выражение rV> эквивалентно выражению 0 + 1*0. Последнее описывает язык, содержащий цепочку 0 и все цепочки, заканчивающиеся символом 0, перед которым стоит произвольное ко­личество единиц. Такой язык также можно определить более простым выражением 1 *0.

Выражение Я® упрощается аналогично рассмотренному выше выражению R[2 ■ Уп­рощение /г',1» и Я® зависит от двух следующих правил, описывающих операции с 0 и выполнимых для любого регулярного выражения R.

0R = R0 = 0, т. е. 0 является нулем (аннулятором) для конкатенации. В результате конкатенации 0, слева или справа, с любым другим выражением получается 0. Это правило очевидно, поскольку для того, чтобы в результате конкатенации получить некоторую цепочку, мы должны взять цепочки из обоих аргументов конкатенации. Если один из аргументов равен 0, выбор цепочки из него становится невозможным. 0+R-R+0 = R, т. е. 0 является единицей для операции объединения. В результа­те объединения любого выражения с 0 получим то же самое выражение.

Итак, выражение 0(Ј + 1)*(Ј + 1) можно заменить 0. После сказанного должны быть по­нятны и два последних упрощения.

Теперь вычислим выражения R. Индуктивное правило для к = 2 имеет следующий вид.

«^«f + j^^j'i»        (3.2)

Если подставим упрощенные выражения из таблицы на рис. 3.5 в уравнение (3.2), то получим выражения, представленные на рис. 3.6. На этом рисунке также приведены уп­рощенные выражения, полученные согласно правилам, описанным для рис. 3.5.