Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 26
Текст из файла (страница 26)
К счастью, существует простой и конечный способ для представления всех подобных цепочек„ а именно, использование регулярных выражений. Таким образом, мы пришли к рассмотрению автоматов, у которых метками являются регулярные выражения. Язык такого автомата представляет собой объединение по всем путям, ведущим от начального к заключительному состоянию, языков, образуемых с помощью конкатенации языков регулярных выражений, расположенных вдоль этих путей. Обратите внимание на то, что это правило согласуется с определением языка для любого рассмотренного выше типа автоматов.
Каждый символ а нли я, если он разрешен, можно рассматривать как регулярное выражение, языком которого является единственная цепочка, т.е. 1а) или (в). Можно принять это замечание за основу описываемой ниже процедуры исключения состояний. На рис. 3.7 показано состояние ж которое мы собираемся исключить. Предположим, что автомат, содержащий ь, содержит состояния д,, дъ ..., дм предшествующие з, и рь ръ ..., р, следующие за х Возможно, некоторые из состояний д совпадают с со- стояниями р, но мы предполагаем, что среди д и р нет з, даже если существует петля, которая начинается и заканчивается в з, как показано на рис.
3.7. Над каждой дугой, ведущей к состоянию з, указано регулярное выражение; дуга, ведущая из состояния 7„помечена выражением 0,. Аналогично, регулярным выражением Р, помечена дуга, ведущая из з в состояние р„лля каждого 1. Петля на з имеет метку о. Наконец, регулярным выражением лз помечена каждая дуга, ведущая нз д, в р, для всех 1 и~. Заметим, что некоторых из этих дуг в автомате может не быть. В этом случае в качестве выражения над дугой используется символ И.
На рис. 3.8 показано, что получится, если исключить состояние ж Все дуги, проходящие через з, удалены. Чтобы это компенсировать, для каждого состояния д„предшествующего А и Для каждого рЬ слеДуюшего за А вводится РегулЯРное выражение, представляющее все пУти, котоРые начинаютсЯ в гуь идУт к А возможно, пРоходЯт петлю на з нУль или несколько раз, и наконец ведут в рг Выражение для таких путей равно ЯЯ Рг Это выражение добавляется (с помощью оператора объединения) к выражению над дугой из 7, в рг Если дуга ~7, — > р, отсутствует, то вначале ей соответствует регулярное выражение Я. 3.2.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ Рис. 3.7. Состояние з, подлежащее исюзючению О 8„, + 0ч5~Р. Рис. 38. Результат иснлючения состояния з из автомата, изображенного на рис, 37 ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ Стратегия построения регулярного выражения по конечному автомату такова. 1. Для каждого допускающего состояния д применить описанный выше процесс сокращения, чтобы построить эквивалентный автомат с дугами, помеченными регулярными выражениями. Исключить все состояния, кроме 9 и начального состояния дв. 2. Если ди йм то должен остаться автомат с двумя состояниями, подобный автомату на рис. 3.9.
Регулярное выражение для допустимых цепочек может быть записано поразному. Один из видов — (й ч- ЯТ7) Я/. Поясним его. Можно переходить из начального состояния в него же любое количество раз, проходя путями, метки которых принадлежат либо Ц)7), либо ЦЯI 7). Выражение ЯЬ Т представляет пути, которые ведут в допускающее состояние по пути с меткой из языка Ц9), затем, возможно, несколько раз проходят через допускающее состояние, используя пути с метками из ЦУ), и наконец возвращаются в начальное состояние, следуя по пути с меткой из ЦТ).
Отсюда нужно перейти в допускающее состояние, уже никогда не возвращаясь в начальное, вдоль пути с меткой из Ц5). Находясь в допускающем состоянии, можно сколько угодно раз вернуться в него по пути с меткой из ЦЩ Начало Рис. 3.9. Обобщенный автомат с двулчя состояниями 3. Если же начальное состояние является допускающим, то необходимо точно так же исключить состояния исходного автомата, удалив все состояния, кроме начального. В результате получим автомат с одним состоянием, подобный представленному на рис. 3.10. Регулярное выражение )1 задает цепочки, допускаемые этим автоматом. Рис. 3. Вх Обобщенный автомат с одни ~ состояниелч 4. Искомое выражение представляет собой сумму (объединение) всех выражений, по- лученных с помощью сокращенного автомата для каждого допускающего состояния согласно правилам 2 и 3.
Пример З.б. Рассмотрим НКА, представленный на рис. 3.11, допускающий цепочки из нулей и единиц, у которых либо на второй, либо на третьей позиции с конца стоит 1. Вначале преобразуем этот автомат в автомат с регулярными выражениями в качестве меток. 3.2. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 117 Пока исключение состояний не производилось, то все, что нам нужно сделать, это заменить метки "О, Г' эквивалентным регулярным выражением О +!. Результат показан на рис. 3. 12. Начал Рис. 3 П НКА, допускаюи!ий цепочки, у которых 7 находится либо на второй, либо на третьей позиции с конца цепочки а+1 Начал Рис.
3! 2. Автомат, изображенный на рис 3 П, с регулярными выражениями в качестве меток Исключим сначала состояние В. Поскольку это состояние не является ни начальным, ни допускающим, то его не будет ни в одном из сокращенных автоматов. Мы избавимся от лишней работы, если исключим это состояние до того, как начнем строить лва сокращенных автомата, соответствующих двум его допускающим состояниям. Существует одно состояние А, предшествующее В, и одно последующее состояние С. Используя обозначения регулярных выражений диаграммь>, представленной на рис.
3.7, получим: Д, = 1, Р, = О м 1, В,~ =- И (потому что из А в С дуги нет) и 5 = И (поскольку нет петли в состоянии В). В результате, выражение над новой дугой из А в С равно И т 1И (0+1). Для сокращения полученного выражения сначала исключаем первый элемент И, который можно игнорировать при объединении. Выражение приобретает вид 1И (О м 1). Напомним, что регулярное выражение И эквивалентно регулярному выражению а, поскольку ЦИ ) = (я) 0 ЦИ) 0 2.(И)1(И) 0 ." Все члены этого объелинения, кроме первого, пусты, поэтому ЦИ ) = (е), что совпадает с Цб).
Следовательно, 1И (О м 1) эквивалентно выражению 1(О ч 1), которое использовано для дуги А — > С на рис. 3.13. аьг Начал Рис. 3АЗ Исключение состояния В Далее нужно по отдельности исключить состояния С и О. Процедура исключения состояния С аналогична описанному выше исключению состояния В, в результате чего получится автомат, представленный на рис. 3.! 4.
ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 118 в+г О Начал Рис. ЗА4. Автомат с двумя состояниями А и 0 В обозначениях обобщенного автомата с двумя состояниями, изображенного на рис.3.9, соответствующие регулярные выражения для рис 3.14 равны; 71= Ом!, 5= 1гО ч-1)(0 ч-1), Т= О и 17= О. Выражение 17 можно заменить на к, те. исключить его из конкатенации, поскольку, как показано выше, Π— я Кроме того, выражение БС Т эквивалентно О, потому что Т вЂ” один из операндов конкатенации — равен Я.
Таким образом, общее выражение (В+Я/Т) Я/ в данном случае упрощается до й Ь; или (Оч-1) 1(Оч-1)(От 1). Говоря неформально, язык этого выражения состоит из цепочек, заканчивающихся единицей с двумя последующими символами, каждый из которых может быть либо нулем, либо единицей. Этот язык представляет одну часть цепочек, которые допускаются автоматом, изображенным на рис. 3.11: у них на третьей позиции с конца стоит 1. Теперь снова нужно вернуться к рис. 3.13 и исключить состояние О. Поскольку в этом автомате нет состояний, следующих за сэ, то согласно рис. 3.7 необходимо лишь удалить дугу, ведущую из С в В, вместе с состоянием В.
В результате получится автомат, показанный на рис. 3.15. в+г Оя Начал Рис. 3 75. Автомат с двумя состояниями, полученный в Результате исключения состояния О Порядок исключения состояний Как было отмечено в примере 3.6, если состояние не является ни начальным, ни допускающим, то оно исключается во всех сокращенных автоматах. Таким образом, одно из преимуществ процесса исключения состояний по сравнению с механической генерацией регулярных выражений, описанной в разделе 3.2А, состоит в том, что сначала мы раз и навсегда исключаем все состояния, которые не являются нн начальными, ни допускающими.
Мы вынуждены повторять процедуру сокращения, только когда необходимо исключить несколько допускающих состояний. Но даже и в этом случае можно совместить некоторые действия процедуры сокрашения. Например, если автомат содержит три допускающих состояния Р, с) и г, то можно вначале исключить л, а затем отдельно исключить либо д, либо г, получив автоматы лля допускающих состояний г и су, соответственно. Затем можно снова начать с трех допускающих состояний и, исключив состояния с7 и г, получить автомат ддя р.
3.2. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 119 Этот автомат очень похож на автомат„изображенный на рис. 3.14; различаются только метки над дугами, ведущими из начального состояния в допускающее. Следовательно, можно применить правило для автомата с двумя состояниями и упростить данное выражение, получив в результате (О + 1)*1(0 + 1). Это выражение представляет другой тип цепочек, допустимых этим автоматом, — цепочки, у которых 1 стоит на второй пози- ции с конца. Осталось объединить оба построенные выражения, чтобы получить следующее выражение для всего автомата (см. рис. 3.11). (О -'; 1) 1(0 ж 1) ь (О е 1)*1(0 -ь 1)(О + 1) С3 3,2.3. Преобразование регулярного выражения в автомат Теперь завершим план, представленный на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
