dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 20
Текст из файла (страница 20)
Но, применяя ее к НКА, построенному по множеству ключевых слов, как в разделе 2.4.2, мы обнаружим, что числосостояний соответствующего ДКА никогда не превосходит числа состояний этого НКА.А поскольку нам известно, что при переходе к ДКА в худшем случае может произойтиэкспоненциальный рост числа состояний, то последнее замечание ободряет и объясняет,почему для распознавания ключевых слов так часто используется метод построения соответствующего НКА, а по нему — ДКА. Правила, в соответствии с которыми строятсясостояния ДКА, состоят в следующем:а) если q0 — начальное состояние НКА, то {q0} — одно из состояний ДКА;б) допустим, p — одно из состояний НКА, и НКА попадает в него из начального состояния по пути, отмеченному символами a1a2…am. Тогда одним из состояний ДКА является множество, состоящее из q0, p и всех остальных состояний НКА, в которые можно попасть из q0 по пути, отмеченному суффиксом (окончанием) цепочки a1a2…am, т.е.
последовательностью символов видаaj aj+1…am.2.4. ÏÐÈËÎÆÅÍÈÅ: ÏÎÈÑÊ Â ÒÅÊÑÒÅСтр. 8787Отметим, что, вообще, всякому состоянию p НКА соответствует одно состояниеДКА. Но на шаге (б) может получиться так, что два состояния на самом деле дают одно ито же множество состояний НКА и поэтому сливаются в одно состояние ДКА. Например, если два ключевых слова начинаются с одной и той же буквы, скажем, a, то два состояния НКА, в которые он попадает из q0 по дуге с меткой a, дают одно и то же множество состояний НКА и, следовательно, сливаются в одно состояние ДКА.Пример 2.15.
На рис. 2.17 показано, как по НКА (см. рис. 2.16) построен ДКА. Каждое из состояний ДКА расположено на том же самом месте, что и состояние p, по которому оно построено, в соответствии с приведенным выше правилом (б). Рассмотрим, например, состояние {1, 3, 5}, обозначенное для краткости как 135. Это состояние былопостроено по состоянию 3. Как и всякое множество состояний нашего ДКА, оно включает состояние 1.
Кроме того, оно включает состояние 5, так как в него автомат попадаетиз 1 по окончанию e цепочки we, приводящей в состояние 3 на рис. 2.16.12135146151617118Рис. 2.17. Преобразовование НКА, изображенного на рис. 2.16, в ДКАДля каждого из состояний ДКА переходы могут быть найдены с помощью конструкции подмножеств.
Но тут можно поступить проще. Для всякого множества состояний,включающего начальное состояние q0 и некоторые другие состояния p1, p2, …, pn, и длякаждого входного символа x вычислим те состояния НКА, в которые по x переходят pi.Тогда данное состояние ДКА, т.е. {q0, p1, p2, …, pn}, будет иметь переход по символу x всостояние ДКА, содержащее q0 и все те состояния, в которые переходят pi. По всем темсимволам x, по которым переходов ни из одного pi нет, данный ДКА будет иметь пере88Стр. 88ÃËÀÂÀ 2.
ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛход по символу x в состояние, содержащее q0 и все те состояния исходного НКА, которые достигаются переходом из q0 по дуге с меткой x.Рассмотрим состояние 135 на рис. 2.17. НКА на рис. 2.16 имеет переходы по символуb из состояний 3 и 5 в состояния 4 и 6, соответственно. Следовательно, 135 по b переходит в 146.
По входному символу e переходов из состояний НКА 3 и 5 нет, но есть переход из 1 в 5. Таким образом, по e ДКА переходит из 135 в 15. Точно так же, по w 135 переходит в 12.По любому другому символу x переходов из состояний 3 и 5 нет, а состояние 1 имеетпереход только в себя. Таким образом, по любому символу из Σ, за исключением b, e иw, 135 переходит в 1. Обозначим это множество как Σ – b – e – w, а также используемподобные обозначения для других множеств, получающихся из Σ удалением несколькихсимволов. 2.4.4. Óïðàæíåíèÿ ê ðàçäåëó 2.42.4.1. Постройте НКА, распознающие следующие множества цепочек:а) (∗) abc, abd и aacd.
Входным алфавитом считать {a, b, c, d};б) 0101, 101 и 011;в) ab, bc и ca. Входным алфавитом считать {a, b, c}.2.4.2. Преобразуйте ваши НКА из упражнения 2.4.1 в ДКА.2.5. Êîíå÷íûå àâòîìàòû ñ ýïñèëîí-ïåðåõîäàìèРассмотрим еще одно обобщение понятия конечного автомата. Придадим автоматуновое “свойство” — возможность совершать переходы по ε, пустой цепочке, т.е. спонтанно, не получая на вход никакого символа.
Эта новая возможность, как и недетерминизм, введенный в разделе 2.3, не расширяет класса языков, допустимых конечными автоматами, но дает некоторое дополнительное “удобство программирования”. Кроме того, рассмотрев в разделе 3.1 регулярные выражения, мы увидим, что последние тесносвязаны с НКА, имеющими ε-переходы. Такие автоматы будем называть ε-НКА.
Ониоказываются полезными при доказательстве эквивалентности между классами языков,задаваемых конечными автоматами и регулярными выражениями.2.5.1. Èñïîëüçîâàíèå ε-ïåðåõîäîâВначале будем оперировать с ε-НКА неформально, используя диаграммы переходов сε в качестве возможной метки. В следующих примерах автомат можно рассматриватькак допускающий последовательности меток, среди которых могут быть ε, вдоль путей2.5.
ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ Ñ ÝÏÑÈËÎÍ-ÏÅÐÅÕÎÄÀÌÈСтр. 8989из начального состояния в допускающее. Но при этом каждое ε вдоль пути “невидимо”,т.е. в последовательность ничего не добавляет.Пример 2.16. На рис. 2.18 изображен ε-НКА, допускающий десятичные числа, которые состоят из следующих элементов.1.Необязательный знак + или −.2.Цепочка цифр.3.Разделяющая десятичная точка.4.Еще одна цепочка цифр. Эта цепочка, как и цепочка (2), может быть пустой, но хотябы одна из них непуста.Началоε,+,−.ε.Рис. 2.18. ε-НКА, допускающий десятичные числаОсобого интереса заслуживает переход из состояния q0 в q1 по любому из символов +, −или ε.
Состояние q1, таким образом, представляет ситуацию, когда прочитан знак числа,если он есть, но не прочитана ни одна из цифр, ни десятичная точка. Состояние q2 соответствует ситуации, когда только что прочитана десятичная точка, а цифры целой частичисла либо уже были прочитаны, либо нет. В состоянии q4 уже наверняка прочитана хотябы одна цифра, но еще не прочитана десятичная точка. Таким образом, q3 интерпретируется как ситуация, когда мы прочитали десятичную точку и хотя бы одну цифру слеваили справа от нее.
Мы можем оставаться в состоянии q3, продолжая читать цифры, номожем и “догадаться”, что цепочка цифр закончена, и спонтанно перейти в допускающеесостояние q5. Пример 2.17. Метод распознавания множества ключевых слов, предложенный впримере 2.14, можно упростить, разрешив ε-переходы. Например, НКА на рис. 2.16,распознающий ключевые слова web и ebay, можно реализовать и с помощью εпереходов, как показано на рис.
2.19. Суть в том, что для каждого ключевого словастроится полная последовательность состояний, как если бы это было единственноеслово, которое автомат должен распознавать. Затем добавляется новое начальное состояние (состояние 9 на рис. 2.19) с ε-переходами в начальные состояния автоматовдля каждого из ключевых слов. 90Стр. 90ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ1230564ε9εНачало782.19.
Использование ε-переходов для распознавания ключевых слов2.5.2. Ôîðìàëüíàÿ çàïèñü ε-ÍÊÀε-НКА можно представлять точно так же, как и НКА, с той лишь разницей, что функция переходов должна содержать информацию о переходах по ε. Формально, ε-НКА Aможно представить в виде A = (Q, Σ, δ, q0, F), где все компоненты имеют тот же смысл,что и для НКА, за исключением δ, аргументами которой теперь являются состояние из Qи элемент множества Σ U{ε}, т.е. либо некоторый входной символ, либо ε.
Никаких недоразумений при этом не возникает, поскольку мы оговариваем, что ε, символ пустойцепочки, не является элементом алфавита Σ.Пример 2.18. ε-НКА на рис. 2.18 можно формально представить какE = ({q0, q1, …, q5}, {., +, −, 0, 1, …, 9}, δ, q0, {q5}),где функция переходов δ определена таблицей переходов на рис.
2.20. ε+, –.0, 1, …, 9q0{q1}{q1}∅∅q1∅∅{q2}{q1, q4}q2∅∅∅{q3}q3{q5}∅∅{q3}q4∅∅{q3}∅q5∅∅∅∅Рис. 2.20. Таблица переходов к рис. 2.182.5.3. ×òî òàêîå ε-çàìûêàíèåДадим формальное определение расширенной функции переходов для ε-НКА, которое приведет к определению допустимости цепочек и языков для данного типа автоматови в конце концов поможет понять, почему ДКА могут имитировать работу ε-НКА. Одна2.5. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ Ñ ÝÏÑÈËÎÍ-ÏÅÐÅÕÎÄÀÌÈСтр. 9191ко прежде нужно определить одно из центральных понятий, так называемое ε-замыканиесостояния. Говоря нестрого, мы получаем ε-замыкание состояния q, совершая все возможные переходы из этого состояния, отмеченные ε.
Но после совершения этих переходов и получения новых состояний снова выполняются ε-переходы, уже из новых состояний, и т.д. В конце концов, мы находим все состояния, в которые можно попасть из q полюбому пути, каждый переход в котором отмечен символом ε. Формально мы определяем ε-замыкание, ECLOSE, рекурсивно следующим образом.Базис. ECLOSE(q) содержит состояние q.Индукция. Если ECLOSE(q) содержит состояние p, и существует переход, отмеченный ε, из состояния p в состояние r, то ECLOSE(q) содержит r.
Точнее, если δ есть функция переходов рассматриваемого ε-НКА и ECLOSE(q) содержит p, то ECLOSE(q) содержит также все состояния из δ(p, ε).Пример 2.19. У автомата, изображенного на рис. 2.18, каждое состояние являетсясобственным ε-замыканием, за исключением того, что ECLOSE(q0) = {q0, q1} иECLOSE(q3) = {q3, q5}.
Это объясняется тем, что имеется лишь два ε-перехода, один изкоторых добавляет q1 в ECLOSE(q0), а другой — q5 в ECLOSE(q3).На рис. 2.21 приведен более сложный пример. Для данного в нем набора состояний,который может быть частью некоторого ε-НКА, мы можем заключить, чтоECLOSE(1) = {1, 2, 3, 4, 6}.2ε3ε6ε1ε45ε7Рис. 2.21. Несколько состояний и переходовВ каждое из этих состояний можно попасть из состояния 1, следуя по пути, отмеченному исключительно ε. К примеру, в состояние 6 можно попасть по пути 1→2→3→6.Состояние 7 не принадлежит ECLOSE(1), поскольку, хотя в него и можно попасть изсостояния 1, в соответствующем пути содержится переход 4→5, отмеченный не ε .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
