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

Прямая подстановка	Упрощенное выражение
R{2)	1*+ 1*0(Ј+0 + 1)*0	1*
г>(2) 12	1*0+ 1*0(Ј+0+ 1)*(Ј+0+ 1)	1*0(0 + 1)*
Ы2) 21	0 + (Ј+0+ 1)(Ј+0 + 1)*0	0
р( 2) 22	Ј + 0 + 1 +(Ј+0 + 1)(Ј + 0 + 1)*(Ј +0+1)	(0+1)*

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

Окончательное регулярное выражение, эквивалентное автомату, представленному на рис. 3.4, строится путем объединения всех тех выражений, для которых первое состояние является начальным, а второе — заключительным. В нашем примере 1 -— начальное со­стояние, а 2 — заключительное, поэтому нам нужно лишь выражение R^), равное 1*0(0 + 1)*. Оно очень просто интерпретируется. Его язык состоит из всех цепочек, начи­нающихся с нулевого или некоторого количества единиц, за которыми следует 0, а за ним — любая цепочка из нулей и единиц. Иначе говоря, это все цепочки из 0 и 1, содер­жащие хотя бы один 0. □

3.2.2. Преобразование ДКА в регулярное выражение методом исключения состояний

Метод преобразования ДКА в регулярное выражение, представленный в разде­ле 3.2.1, работает всегда. Как вы, возможно, заметили, он на самом деле не зависит от того, детерминирован ли этот автомат, и точно так же применим и к НКА, и даже к е - НКА. Однако такой метод построения регулярного выражения очень трудоемок. Не только потому, что для автомата с п состояниями необходимо построить порядка п вы­ражений, но и потому, что с каждым из п шагов индукции длина выражения может воз­растать в среднем в четыре раза, если эти выражения не упрощать. Таким образом, раз­меры результирующих выражений могут достигать порядка 4" символов.

Существует аналогичный метод, избавляющий от некоторых повторных действий. Например, во всех выражениях с верхним индексом (к) в доказательстве теоремы 3.4 ис­пользуется одно и то же подвыражение (R. fk~l) )*, которое приходится выписывать в об­щей сложности п2 раз.

Метод построения регулярных выражений, который мы изучим в этом разделе, пред­полагает исключение состояний. Если исключить некоторое состояние s, то все пути ав­томата, проходящие через это состояние, исчезают. Для того чтобы язык автомата при этом не изменился, необходимо написать на дуге, ведущей непосредственно из некото­рого состояния q в состояние р, метки всех тех путей, которые вели из состояния q в со­стояние р, проходя через состояние s. Поскольку теперь метка такой дуги будет содер­жать цепочки, а не отдельные символы, и таких цепочек может быть даже бесконечно много, то мы не можем просто записать список этих цепочек в качестве метки. К сча­стью, существует простой и конечный способ для представления всех подобных цепочек, а именно, использование регулярных выражений.

Таким образом, мы пришли к рассмотрению автоматов, у которых метками являются регулярные выражения. Язык такого автомата представляет собой объединение по всем путям, ведущим от начального к заключительному состоянию, языков, образуемых с по­мощью конкатенации языков регулярных выражений, расположенных вдоль этих путей. Обратите внимание на то, что это правило согласуется с определением языка для любого рассмотренного выше типа автоматов. Каждый символ а или Ј, если он разрешен, можно рассматривать как регулярное выражение, языком которого является единственная це­почка, т. е. {а} или {Ј}. Можно принять это замечание за основу описываемой ниже про­цедуры исключения состояний.

На рис. 3.7 показано состояние s, которое мы собираемся исключить. Предполо­жим, что автомат, содержащий j, содержит состояния qh q2, ..., qu, предшествующие j, и Ри Pi, ...,Рпи следующие за s. Возможно, некоторые из состояний q совпадают с со­стояниями р, но мы предполагаем, что среди q и р нет s, даже если существует петля, ко­торая начинается и заканчивается в s, как показано на рис. 3.7. Над каждой дугой, веду­щей к состоянию s, указано регулярное выражение; дуга, ведущая из состояния qt, поме­чена выражением Qi. Аналогично, регулярным выражением Р{ помечена дуга, ведущая из s в состояние р\, для каждого г. Петля на s имеет метку S. Наконец, регулярным выраже­нием помечена каждая дуга, ведущая из qx в pt для всех i и j. Заметим, что некоторых из этих дуг в автомате может не быть. В этом случае в качестве выражения над дугой ис­пользуется символ 0.

На рис. 3.8 показано, что получится, если исключить состояние s. Все дуги, проходящие через s, удалены. Чтобы это компенсировать, для каждого состояния <у„ предшествующего s, и для каждого рр следующего за s, вводится регулярное выражение, представляющее все пути, которые начинаются в q-„ идут к s, возможно, проходят петлю на s нуль или несколько раз, и наконец ведут в ру Выражение для таких путей равно Q\S*Py Это выражение добавля­ется (с помощью оператора объединения) к выражению над дугой из q\ в ру Если дуга <7; —> pi отсутствует, то вначале ей соответствует регулярное выражение 0.

Рис. 3.7. Состояние s, подлежащее исключению

Рис. 3.8. Результат исключения состояния s из автомата, изображенного на рис. 3.7

Стратегия построения регулярного выражения по конечному автомату такова.

1. Для каждого допускающего состояния q применить описанный выше процесс сокра­щения, чтобы построить эквивалентный автомат с дугами, помеченными регулярными выражениями. Исключить все состояния, кроме q и начального состояния q0.

1. Если q Ф q0, то должен остаться автомат с двумя состояниями, подобный автомату на рис. 3.9. Регулярное выражение для допустимых цепочек может быть записано по - разному. Один из видов — (R + SU*T)*SU*. Поясним его. Можно переходить из на­чального состояния в него же любое количество раз, проходя путями, метки которых принадлежат либо L(R), либо L(SU*T). Выражение SU*T представляет пути, которые ведут в допускающее состояние по пути с меткой из языка L(S), затем, возможно, несколько раз проходят через допускающее состояние, используя пути с метками из L(U), и наконец возвращаются в начальное состояние, следуя по пути с меткой из 1(7). Отсюда нужно перейти в допускающее состояние, уже никогда не возвращаясь в начальное, вдоль пути с меткой из L(S). Находясь в допускающем состоянии, мож­но сколько угодно раз вернуться в него по пути с меткой из L(U).

Рис. 3.9. Обобщенный автомат с двумя состояниями

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

R

4. Искомое выражение представляет собой сумму (объединение) всех выражений, по­лученных с помощью сокращенного автомата для каждого допускающего состояния согласно правилам 2 и 3.

Пример 3.6. Рассмотрим НКА, представленный на рис. 3.11, допускающий цепочки из нулей и единиц, у которых либо на второй, либо на третьей позиции с конца стоит 1. Вна­чале преобразуем этот автомат в автомат с регулярными выражениями в качестве меток.

Пока исключение состояний не производилось, то все, что нам нужно сделать, это заменить метки "О, 1" эквивалентным регулярным выражением 0+1. Результат показан на рис. 3.12.

о, 1

Начало

0,1

0, 1

0        1 /""Л

0 + 1

Рис. 3.12. Автомат, изображенный нарис. 3.11, с регулярными выражениями в качестве меток

Исключим сначала состояние В. Поскольку это состояние не является ни начальным, ни допускающим, то его не будет ни в одном из сокращенных автоматов. Мы избавимся от лишней работы, если исключим это состояние до того, как начнем строить два сокра­щенных автомата, соответствующих двум его допускающим состояниям.

Существует одно состояние А, предшествующее В, и одно последующее состояние С. Используя обозначения регулярных выражений диаграммы, представленной на рис. 3.7, получим: Qi = 1, Р\ = 0 + 1, Rn = 0 (потому что из А в С дуги нет) и 5=0 (поскольку нет петли в состоянии В). В результате, выражение над новой дугой из А в С равно 0 + 10*(О + 1).

Для сокращения полученного выражения сначала исключаем первый элемент 0, кото­рый можно игнорировать при объединении. Выражение приобретает вид 10*(О + 1). На­помним, что регулярное выражение 0* эквивалентно регулярному выражению Ј, поскольку

Рис. 3.11. НКА, допускающий цепочки, у которых 1 находится либо на второй, либо на третьей позиции с конца цепочки

1(0*) = {Ј} и Ц0) и Ц0)Ц0) и...

Все члены этого объединения, кроме первого, пусты, поэтому 1(0*) = {Ј}, что совпа­дает с L(e). Следовательно, 10*(О+1) эквивалентно выражению 1(0+1), которое ис­пользовано для дуги А —> С на рис. 3.13.

0 + 1

Рис. 3.13. Исключение состояния В

Далее нужно по отдельности исключить состояния С и D. Процедура исключения со­стояния С аналогична описанному выше исключению состояния В, в результате чего по­лучится автомат, представленный на рис. 3.14.

0 + 1