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

Рис. 3.14. Автомат с двумя состояниями А и D

В обозначениях обобщенного автомата с двумя состояниями, изображенного на рис. 3.9, соответствующие регулярные выражения для рис. 3.14 равны: R= 0+1, S - 1(0 + 1)(0 + 1), Т= 0 и {/=0. Выражение U* можно заменить на Ј, т. е. исключить его из конкатенации, поскольку, как показано выше, 0* = е. Кроме того, выражение SU*T эквивалентно 0, потому что Т— один из операндов конкатенации— равен 0. Таким образом, общее выражение (R + SUT) SU в данном случае упрощается до R S, или (0 + 1)1(0 + 1)(0 + 1). Говоря неформально, язык этого выражения состоит из цепочек, заканчивающихся единицей с двумя последующими символами, каждый из которых мо­жет быть либо нулем, либо единицей. Этот язык представляет одну часть цепочек, кото­рые допускаются автоматом, изображенным на рис. 3.11: у них на третьей позиции с конца стоит 1.

Теперь снова нужно вернуться к рис. 3.13 и исключить состояние D. Поскольку в этом автомате нет состояний, следующих за D, то согласно рис. 3.7 необходимо лишь удалить дугу, ведущую из С в D, вместе с состоянием D. В результате получится автомат, показанный на рис. 3.15.

0 + 1

Начало 1(0 +1) S/^S        Aj                ►ПСП

Рис. 3.15. Автомат с двумя состояниями, полученный в результате исключения состояния D

Порядок исключения состояний

Как было отмечено в примере 3.6, если состояние не является ни начальным, ни до­пускающим, то оно исключается во всех сокращенных автоматах. Таким образом, одно из преимуществ процесса исключения состояний по сравнению с механической генерацией регулярных выражений, описанной в разделе 3.2.1, состоит в том, что сначала мы раз и навсегда исключаем все состояния, которые не являются ни началь­ными, ни допускающими. Мы вынуждены повторять процедуру сокращения, только когда необходимо исключить несколько допускающих состояний. Но даже и в этом случае можно совместить некоторые действия процедуры сокраще­ния. Например, если автомат содержит три допускающих состояния р, q кг, то можно вначале исключить р, а затем отдельно исключить либо q, либо г, получив автоматы для допускающих состояний г и q, соответственно. Затем можно снова начать с трех допускающих состояний и, исключив состояния q и г, получить автомат для р.

Этот автомат очень похож на автомат, изображенный на рис. 3.14; различаются толь­ко метки над дугами, ведущими из начального состояния в допускающее. Следовательно, можно применить правило для автомата с двумя состояниями и упростить данное выра­жение, получив в результате (0 + 1)*1(0 + 1). Это выражение представляет другой тип цепочек, допустимых этим автоматом, — цепочки, у которых 1 стоит на второй пози­ции с конца.

Осталось объединить оба построенные выражения, чтобы получить следующее вы­ражение для всего автомата (см. рис. 3.11).

(О + 1)*1(0 + 1) + (0 + 1)*1(0 + 1)(0 + 1)

□

3.2.3. Преобразование регулярного выражения в автомат

Теперь завершим план, представленный на рис. 3.1, показав, что любой язык L, яв­ляющийся языком L(R) для некоторого регулярного выражения R, будет также языком ЦЕ) для некоторого Ј-НК доказательство проведем методом структурной ин­дукции по выражению R. Сначала покажем, как строить автоматы для базовых выраже­ний: отдельных символов, Ј и 0. Затем опишем, каким образом объединять эти автоматы в большие автоматы, которые допускают объединение, конкатенацию или итерацию языков, допускаемых меньшими автоматами.

Все конструируемые автоматы представляют собой Ј-НКА с одним допускающим со­стоянием.

Теорема 3.7. Любой язык, определяемый регулярным выражением, можно задать не­которым конечным автоматом.

Доказательство. Предположим, что L = L(R) для регулярного выражения R. Пока­жем, что L = L(E) для некоторого Ј-НКА Е, обладающего следующими свойствами.

Он имеет ровно одно допускающее состояние. У него нет дуг, ведущих в начальное состояние. У него нет дуг, выходящих из допускающего состояния.

Доказательство проводится структурной индукцией по выражению R, следуя рекур­сивному определению регулярных выражений из раздела 3.1.2.

Базис. Базис состоит из трех частей, представленных на рис. 3.16. В части (а) рас­сматривается выражение е. Языком такого автомата является {е}, поскольку единствен­ный путь из начального в допускающее состояние помечен выражением Ј. В части (б) показана конструкция для 0. Понятно, что, поскольку отсутствуют пути из начального состояния в допускающее, языком этого автомата будет 0. Наконец, в части (в) пред­ставлен автомат для регулярного выражения а. Очевидно, что язык этого автомата со­стоит из одной цепочки а и равен L(а). Кроме того, все эти автоматы удовлетворяют ус­ловиям (1), (2) и (3) индуктивной гипотезы.

       /

©

       V        /

б)

       V        У

В)

Рис. 3.16. Базис построения автомата по регулярному выражению

Индукция. Три части индукции представлены на рис. 3.17. Предположим, что ут­верждение теоремы истинно для непосредственных подвыражений данного регулярного выражения, т. е. языки этих подвыражений являются также языками Ј-НКА с единствен­ным допускающим состоянием. Возможны четыре случая.

Данное выражение имеет вид R + S для некоторых подвыражений R и S. Тогда ему соответствует автомат, представленный на рис. 3.17, а. В этом автомате из нового начального состояния можно перейти в начальное состояние автомата для выраже­ния либо R, либо S. Затем мы попадаем в допускающее состояние одного из этих ав­томатов, следуя по пути, помеченному некоторой цепочкой из языка L(R) или L(S), соответственно. Попав в допускающее состояние автомата для R или S, можно по одному из Ј-путей перейти в допускающее состояние нового автомата. Следователь­но, язык автомата, представленного на рис. 3.17, а, равен L(R) (J L(S). Выражение имеет вид RS для некоторых подвыражений R и S. Автомат для этой конкатенации представлен на рис. 3.17, б. Отметим, что начальное состояние перво­го автомата становится начальным состоянием для всего автомата, представляющего конкатенацию, а допускающим для него будет допускающее состояние второго ав­томата. Идея состоит в том, что путь, ведущий из начального в допускающее со­стояние, сначала проходит через автомат для R по некоторому пути, помеченному цепочкой из L(R), а потом — через автомат для S по пути, помеченному цепочкой из L(S). Следовательно, путями автомата, представленного на рис. 3.17, б, будут те и только те пути, которые помечены цепочками из языка L(R)L(S>). Выражение имеет вид R* для некоторого подвыражения R. Используем автомат, пред­ставленный на рис. 3.17, е. Этот автомат позволяет пройти по следующим путям:

а)        из начального состояния непосредственно в допускающее по пути, помечен­ному е. Этот путь позволяет допустить цепочку е, которая принадлежит L(R*) независимо от выражения R;

б)        перейти в начальное состояние автомата для R, пройти через этот автомат один или несколько раз, и затем попасть в допускающее состояние. Это множество путей дает возможность допускать цепочки, которые принадле­жат языкам L(R), L(R)L(R), L(R)L(R)L( R) и так далее, порождая таким обра­зом все цепочки из Ј(/?*), за исключением, возможно, цепочки е. Но она по­лучена в п. 3, а как отметка дуги непосредственно из начального в допус­кающее состояние.

4. Выражение имеет вид (R) для некоторого подвыражения R. Автомат для R мо­жет быть автоматом и для (R), поскольку скобки не влияют на язык, задаваемый выражением.

б)

Рис. 3.17. Индуктивный шаг преобразования регулярного выражения в е-НКА

Легко заметить, что построенные автоматы удовлетворяют всем трем условиям ин­дуктивной гипотезы: одно допускающее состояние, отсутствие дуг, ведущих в начальное состояние, и дуг, выходящих из допускающего состояния. □

Пример 3.8. Преобразуем регулярное выражение (0 + 1)*1(0 + 1) в Ј-НКА. Постро­им сначала автомат для 0 + 1. Для этого используем два автомата, построенные со­гласно рис. 3.16, в: один с меткой 0 на дуге, другой— с меткой 1. Эти автоматы со­единены с помощью конструкции объединения (см. рис. 3.17, а). Результат изображен на рис. 3.18, а.

Рис. 3.18. Автомат, построенный для примера 3.8

Далее, применим к автомату (см. рис. 3.18, а) конструкцию итерации (см. рис. 3.17, в). Полученный автомат изображен на рис. 3.18, б. На последних двух ша­гах применяется конструкция конкатенации (см. рис. 3.17, б). Сначала автомат, представленный на рис. 3.18, б, соединяется с автоматом, допускающим только це­почку 1. Последний получается путем еще одного применения базисной конструк­ции (см. рис. 3.16, в) с меткой 1 на дуге. Отметим, что для распознавания цепочки 1 необходимо создать новый автомат; здесь нельзя использовать автомат для 1, являю­щийся частью автомата, изображенного на рис. 3.18, а. Третьим автоматом в конкате­нации будет еще один автомат для выражения 0+1. Опять-таки, необходимо создать копию автомата (см. рис. 3.18, а), поскольку нельзя использовать автомат для 0+1, представляющий собой часть автомата (см. рис. 3.18, б).

Полный автомат показан на рис. 3.18, е. Заметим, что если удалить е-переходы, то этот е-НКА будет весьма похож на более простой автомат (см. рис. 3.15), также допус­кающий цепочки с 1 на предпоследней позиции. □