dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 26
Текст из файла (страница 26)
3.8 показано, что получится, если исключить состояние s. Все дуги, проходящиечерез s, удалены. Чтобы это компенсировать, для каждого состояния qi, предшествующегоs, и для каждого pj, следующего за s, вводится регулярное выражение, представляющее всепути, которые начинаются в qi, идут к s, возможно, проходят петлю на s нуль или несколькораз, и наконец ведут в pj. Выражение для таких путей равно QiS*Pj.
Это выражение добавляется (с помощью оператора объединения) к выражению над дугой из qi в pj. Если дугаqi → pj отсутствует, то вначале ей соответствует регулярное выражение ∅.3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 115115Рис. 3.7. Состояние s, подлежащее исключениюРис. 3.8. Результат исключения состояния s из автомата, изображенного на рис. 3.7116Стр.
116ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈСтратегия построения регулярного выражения по конечному автомату такова.1.Для каждого допускающего состояния q применить описанный выше процесс сокращения, чтобы построить эквивалентный автомат с дугами, помеченными регулярнымивыражениями. Исключить все состояния, кроме q и начального состояния q0.2.Если q ≠ q0, то должен остаться автомат с двумя состояниями, подобный автомату нарис. 3.9.
Регулярное выражение для допустимых цепочек может быть записано поразному. Один из видов — (R + SU*T)*SU*. Поясним его. Можно переходить из начального состояния в него же любое количество раз, проходя путями, метки которыхпринадлежат либо L(R), либо L(SU*T). Выражение SU*T представляет пути, которыеведут в допускающее состояние по пути с меткой из языка L(S), затем, возможно,несколько раз проходят через допускающее состояние, используя пути с метками изL(U), и наконец возвращаются в начальное состояние, следуя по пути с меткой изL(T).
Отсюда нужно перейти в допускающее состояние, уже никогда не возвращаясьв начальное, вдоль пути с меткой из L(S). Находясь в допускающем состоянии, можно сколько угодно раз вернуться в него по пути с меткой из L(U).НачалоРис. 3.9. Обобщенный автомат с двумя состояниями3.Если же начальное состояние является допускающим, то необходимо точно так жеисключить состояния исходного автомата, удалив все состояния, кроме начального.В результате получим автомат с одним состоянием, подобный представленному нарис.
3.10. Регулярное выражение R* задает цепочки, допускаемые этим автоматом.НачалоРис. 3.10. Обобщенный автомат с одним состоянием4.Искомое выражение представляет собой сумму (объединение) всех выражений, полученных с помощью сокращенного автомата для каждого допускающего состояниясогласно правилам 2 и 3.Пример 3.6. Рассмотрим НКА, представленный на рис. 3.11, допускающий цепочки изнулей и единиц, у которых либо на второй, либо на третьей позиции с конца стоит 1.
Вначале преобразуем этот автомат в автомат с регулярными выражениями в качестве меток.3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 117117Пока исключение состояний не производилось, то все, что нам нужно сделать, это заменитьметки “0, 1” эквивалентным регулярным выражением 0 + 1. Результат показан на рис. 3.12.НачалоРис.
3.11. НКА, допускающий цепочки, у которых 1 находится либо на второй, либона третьей позиции с конца цепочкиНачалоРис. 3.12. Автомат, изображенный на рис. 3.11, с регулярными выражениями в качестве метокИсключим сначала состояние B. Поскольку это состояние не является ни начальным,ни допускающим, то его не будет ни в одном из сокращенных автоматов. Мы избавимсяот лишней работы, если исключим это состояние до того, как начнем строить два сокращенных автомата, соответствующих двум его допускающим состояниям.Существует одно состояние А, предшествующее B, и одно последующее состояние C.Используя обозначения регулярных выражений диаграммы, представленной на рис. 3.7,получим: Q1 = 1, P1 = 0 + 1, R11 = ∅ (потому что из A в C дуги нет) и S = ∅ (посколькунет петли в состоянии B).
В результате, выражение над новой дугой из A в C равно ∅ +1∅*(0 + 1).Для сокращения полученного выражения сначала исключаем первый элемент ∅, который можно игнорировать при объединении. Выражение приобретает вид 1∅*(0 + 1). Напомним, что регулярное выражение ∅* эквивалентно регулярному выражению ε, посколькуL(∅*) = {ε} U L(∅) U L(∅)L(∅) U …Все члены этого объединения, кроме первого, пусты, поэтому L(∅*) = {ε}, что совпадает с L(ε). Следовательно, 1∅*(0 + 1) эквивалентно выражению 1(0 + 1), которое использовано для дуги A → C на рис. 3.13.НачалоРис.
3.13. Исключение состояния BДалее нужно по отдельности исключить состояния C и D. Процедура исключения состояния C аналогична описанному выше исключению состояния B, в результате чего получится автомат, представленный на рис. 3.14.118Стр. 118ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈНачалоРис. 3.14.
Автомат с двумя состояниями A и DВ обозначениях обобщенного автомата с двумя состояниями, изображенного нарис. 3.9, соответствующие регулярные выражения для рис. 3.14 равны: R = 0 + 1,S = 1(0 + 1)(0 + 1), T = ∅ и U = ∅. Выражение U* можно заменить на ε, т.е. исключитьего из конкатенации, поскольку, как показано выше, ∅* = ε. Кроме того, выражение SU*Tэквивалентно ∅, потому что T — один из операндов конкатенации — равен ∅. Такимобразом, общее выражение (R + SU*T)*SU* в данном случае упрощается до R*S, или(0 + 1)*1(0 + 1)(0 + 1).
Говоря неформально, язык этого выражения состоит из цепочек,заканчивающихся единицей с двумя последующими символами, каждый из которых может быть либо нулем, либо единицей. Этот язык представляет одну часть цепочек, которые допускаются автоматом, изображенным на рис. 3.11: у них на третьей позиции сконца стоит 1.Теперь снова нужно вернуться к рис. 3.13 и исключить состояние D. Поскольку вэтом автомате нет состояний, следующих за D, то согласно рис. 3.7 необходимо лишьудалить дугу, ведущую из C в D, вместе с состоянием D. В результате получится автомат,показанный на рис.
3.15.НачалоРис. 3.15. Автомат с двумя состояниями, полученный в результате исключения состояния DÏîðÿäîê èñêëþ÷åíèÿ ñîñòîÿíèéКак было отмечено в примере 3.6, если состояние не является ни начальным, ни допускающим, то оно исключается во всех сокращенных автоматах. Таким образом,одно из преимуществ процесса исключения состояний по сравнению с механическойгенерацией регулярных выражений, описанной в разделе 3.2.1, состоит в том, чтосначала мы раз и навсегда исключаем все состояния, которые не являются ни начальными, ни допускающими.
Мы вынуждены повторять процедуру сокращения, толькокогда необходимо исключить несколько допускающих состояний.Но даже и в этом случае можно совместить некоторые действия процедуры сокращения. Например, если автомат содержит три допускающих состояния p, q и r, то можновначале исключить p, а затем отдельно исключить либо q, либо r, получив автоматыдля допускающих состояний r и q, соответственно. Затем можно снова начать с трехдопускающих состояний и, исключив состояния q и r, получить автомат для p.3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 119119Этот автомат очень похож на автомат, изображенный на рис. 3.14; различаются только метки над дугами, ведущими из начального состояния в допускающее. Следовательно,можно применить правило для автомата с двумя состояниями и упростить данное выражение, получив в результате (0 + 1)*1(0 + 1).
Это выражение представляет другой типцепочек, допустимых этим автоматом, — цепочки, у которых 1 стоит на второй позиции с конца.Осталось объединить оба построенные выражения, чтобы получить следующее выражение для всего автомата (см. рис. 3.11).(0 + 1)*1(0 + 1) + (0 + 1)*1(0 + 1)(0 + 1)3.2.3. Ïðåîáðàçîâàíèå ðåãóëÿðíîãî âûðàæåíèÿ â àâòîìàòТеперь завершим план, представленный на рис. 3.1, показав, что любой язык L, являющийся языком L(R) для некоторого регулярного выражения R, будет также языкомL(E) для некоторого ε-НКА E.
Это доказательство проведем методом структурной индукции по выражению R. Сначала покажем, как строить автоматы для базовых выражений: отдельных символов, ε и ∅. Затем опишем, каким образом объединять эти автоматыв большие автоматы, которые допускают объединение, конкатенацию или итерациюязыков, допускаемых меньшими автоматами.Все конструируемые автоматы представляют собой ε-НКА с одним допускающим состоянием.Теорема 3.7.
Любой язык, определяемый регулярным выражением, можно задать некоторым конечным автоматом.Доказательство. Предположим, что L = L(R) для регулярного выражения R. Покажем, что L = L(E) для некоторого ε-НКА E, обладающего следующими свойствами.1.Он имеет ровно одно допускающее состояние.2.У него нет дуг, ведущих в начальное состояние.3.У него нет дуг, выходящих из допускающего состояния.Доказательство проводится структурной индукцией по выражению R, следуя рекурсивному определению регулярных выражений из раздела 3.1.2.Базис.
Базис состоит из трех частей, представленных на рис. 3.16. В части (а) рассматривается выражение ε. Языком такого автомата является {ε}, поскольку единственный путь из начального в допускающее состояние помечен выражением ε. В части (б)показана конструкция для ∅.
Понятно, что, поскольку отсутствуют пути из начальногосостояния в допускающее, языком этого автомата будет ∅. Наконец, в части (в) представлен автомат для регулярного выражения а. Очевидно, что язык этого автомата состоит из одной цепочки a и равен L(a). Кроме того, все эти автоматы удовлетворяют условиям (1), (2) и (3) индуктивной гипотезы.120Стр.
120ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈεа)б)ав)Рис. 3.16. Базис построения автомата по регулярному выражениюИндукция. Три части индукции представлены на рис. 3.17. Предположим, что утверждение теоремы истинно для непосредственных подвыражений данного регулярноговыражения, т.е. языки этих подвыражений являются также языками ε-НКА с единственным допускающим состоянием. Возможны четыре случая.1.2.3.Данное выражение имеет вид R + S для некоторых подвыражений R и S. Тогда емусоответствует автомат, представленный на рис. 3.17, а. В этом автомате из новогоначального состояния можно перейти в начальное состояние автомата для выражения либо R, либо S. Затем мы попадаем в допускающее состояние одного из этих автоматов, следуя по пути, помеченному некоторой цепочкой из языка L(R) или L(S),соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
