И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 7
Текст из файла (страница 7)
у нетерминалов A и B есть одинаковые правые части — Bb).Такой грамматике будет соответствовать недетерминированный конечный автомат.Определение: недетерминированный конечный автомат (НКА) — это пятерка 〈 K, T,δ, H, S 〉, гдеK — конечное множество состояний;T — конечное множество допустимых входных символов;δ — отображение множества K × T в множество подмножеств K;H ⊂ K — конечное множество начальных состояний;S ⊂ K — конечное множество заключительных состояний.δ(A, t) = {B1, B2,..., Bn} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний Bi, i = 1, 2, ..., n. Также как и ДКА, любой НКА можнопредставить в виде таблицы (в одной ячейке такой таблицы можно указывать сразу несколько состояний, в которые возможен переход из заданного состояния по текущему символу)или в виде диаграммы состояний (ДС).
В ДС каждому состоянию из множества K соответствует вершина; из вершины A в вершину B ведет дуга, помеченная символом t, еслиB ∈ δ (A, t). (В НКА из одной вершины могут исходить несколько дуг с одинаковой пометкой). Успешный путь — это путь из начальной вершины в заключительную; пометка пути— это последовательность пометок его дуг. Язык, допускаемый НКА, — это множество пометок всех успешных путей.Если начальное состояние автомата (НКА или ДКА) одновременно является и заключительным, то автомат допускает пустую цепочку ε.ЗамечаниеАвтомат, построенный по регулярной грамматике без пустых правых частей, не допускает ε.Для построения разбора по регулярной грамматике в недетерминированном случаеможно предложить алгоритм, который будет перебирать все возможные варианты сверток(переходов) один за другим; если цепочка принадлежит языку, то будет найден успешныйпуть; если каждый из просмотренных вариантов завершится неудачей, то цепочка языку непринадлежит.
Однако такой алгоритм практически неприемлем, поскольку при переборе вариантов мы, скорее всего, снова окажемся перед проблемой выбора и, следовательно, будемиметь «дерево отложенных вариантов» и экспоненциальный рост сложности разбора.Один из наиболее важных результатов теории конечных автоматов состоит в том,что класс языков, определяемых недетерминированными конечными автоматами, совпадаетс классом языков, определяемых детерминированными конечными автоматами.29Элементы теории трансляции / Разбор по регулярным грамматикамУтверждение 10.
Пусть L — формальный язык. Следующие утверждения эквивалентны:(1) L порождается регулярной грамматикой;(2) L допускается ДКА;(3) L допускается НКА.Эквивалентность пунктов (1) и (2) следует из рассмотренных выше алгоритмов построения конечного автомата по регулярной грамматике и обратно — грамматики по автомату. Очевидно, что из (2) следует (3): достаточно записать вместо каждого перехода ДКАδ(C, a) = b эквивалентный ему переход в НКА δ(C, a) = {b}, начальное состояние ДКА поместить в множество начальных состояний НКА, а заключительное состояние ДКА поместить в множество заключительных состояний НКА. Приводимый ниже алгоритм построенияДКА, эквивалентного НКА, обосновывает то, что из (3) следует (2).Алгоритм построения ДКА по НКАВход: НКА M = 〈 K, T, δ, H, S 〉 .Выход: ДКА M1 = 〈 K1, T, δ1, H1, S1 〉, допускающий тот же язык, что и автомат М :L(M) = L(M1).Метод:1.
Элементами K1, т. е. состояниями в ДКА, будут некоторые подмножества множества состояний НКА. Заметим, что в силу конечности множества K, множество K1 также коsнечно и имеет не более 2 элементов, где s — мощность K.Подмножество {А1, A2, …, An} состояний из К будем для краткости записывать какA1A2...An. Множество K1 и переходы, определяющие функцию δ1, будем строить, начиная ссостояния H1: H1 := A1A2...An, где А1, A2, …, An ∈ H.
Другими словами, все начальные состояния НКА M объединяются в одно состояние H1 для ДКА M1. Добавляем в множество K1 построенное начальное состояние H1 и пока считаем его нерассмотренным (на втором шаге онорассматривается и строятся остальные состояния множества K1, а также переходы δ1 .)2. Пока в K1 есть нерассмотренный элемент A1A2...Am, «рассматриваем» его и выполняем для каждого t ∈ T следующие действия: Полагаем δ1 ( A1A2...Am, t ) = B1B2...Bk, где для 1 ≤ j ≤ k в НКА δ (Ai, t) = Bj для неко-торых 1 ≤ i ≤ m.
Другими словами, B1B2...Bk — это множество всех состояний вНКА, куда можно перейти по символу t из множества состояний A1A2...Am. В ДКАM1 получается детерминированный переход по символу t из состояния A1A2...Am всостояние B1B2...Bk. (Если k = 0, то полагаем δ1 ( A1A2...Am, t ) = ∅ ). Добавляем в K1 новое состояние B1B2...Bk .Шаг 2 завершается, поскольку множество новых состояний K1 конечно.3. Заключительными состояниями построенного ДКА M1 объявляются все состояния,содержащие в себе хотя бы одно заключительное состояние НКА M: S1 := {A1A2...Am |A1A2...Am ∈ K1, Ai ∈ S для некоторых 1 ≤ i ≤ m}.ЗамечаниеМножество S1 построенного ДКА может состоять более, чем из одного элемента. Не для всех регулярных языков существует ДКА с единственным заключительным состоянием (пример: языквсех цепочек в алфавите {a, b}, содержащих не более двух символов b).
Однако для реализации30Элементы теории трансляции / Разбор по регулярным грамматикамалгоритма детерминированного разбора заключительное состояние должно быть единственным.В таком случае изменяют входной язык, добавляя маркер ⊥ в конец каждой цепочки (на практикев роли маркера конца цепочки ⊥ может выступать признак конца файла, символ конца строкиили другие разделители). Вводится новое состояние S, и для каждого состояния Q из множестваS1 добавляется переход по символу ⊥: δ1 (Q, ⊥) = S. Состояния из S1 больше не считаются заключительными, а S объявляется единственным заключительным состоянием. Теперь по такомуДКА можно построить автоматную грамматику, допускающую детерминированный разбор.Проиллюстрируем работу алгоритма на примерах.Пример 1.
Задан НКА M = 〈{ H, A, B, S }, {0, 1}, δ, {H }, {S } 〉, гдеδ(H, 1) = {B}δ(A, 1) = {B, S}δ(B, 0) = { A }nL(M) = { 1(01) | n ≥ 1 }.Диаграмма для M изображена на рис.7.H1B10A1SРис. 7. ДС для автомата M.Грамматика, соответствующая M:S → A1A → B0B → A1 | 1Построим ДКА по НКА, пользуясь предложенным алгоритмом. Начальным состоянием будет H.δ1(Н, 1) = Bδ1(B, 0) = Aδ1(A, 1) = BSδ1(BS, 0) = AЗаключительным состоянием построенного ДКА является состояние BS.Таким образом, M1 = 〈 {H, B, A, BS }, {0, 1}, δ1, H, BS 〉. Для удобства переименуем состояния в M1 : BS обозначается теперь как S1, а в однобуквенных именах состояний вместоподчеркивания используется индекс 1.
Тогда M1 = 〈 {H1, B1, A1, S1}, {0, 1}, { δ1(Н1, 1) = B1;δ1(B1, 0) = A1; δ1(A1, 1) = S1; δ1(S1, 0) = A1}, H1, S1〉.Грамматика, соответствующая M1:S1 → A11A1 → S10 | B10B1 → 1Построим диаграмму состояний (рис. 8).31Элементы теории трансляции / Разбор по регулярным грамматикам1H1B10A101S1Рис. 8. Диаграмма состояний M1.Пример 2. Дана регулярная грамматика G = 〈 T, N, P, S 〉P:S → Sb | Aa | aA → Aa | Sb | b,которой соответствует НКА.
С помощью преобразования НКА в ДКА построить грамматику,по которой возможен детерминированный разбор.РешениеПостроим функцию переходов НКА:δ(H, a) = {S}δ(H, b) = {A}δ(A, a) = {A, S}δ(S, b) = {A, S}Процесс построения функции переходов ДКА удобно изобразить в виде таблицы, начав ее заполнение с начального состояния H, добавляя строки для вновь появляющихся состояний:символabHSAS∅ASAAS∅ASASASсостояниеПереходы ДКА:δ1(H, a) = Sδ1(H, b) = Aδ1 (S, b) = ASδ1(A, a) = ASδ1(AS, a) = ASδ1(AS, b) = AS32появилисьсотояния S и A ,они рассматриваются в следующих строкахтаблицыЭлементы теории трансляции / Разбор по регулярным грамматикамПереобозначим сотояния: A ⇒ A, H ⇒ H, AS ⇒ Y, S ⇒ X.
Два заключительныхсостояния X и Y сведем в одно заключительное состояние S, используя маркер конца цепочки ⊥. После такой модификации получаем ДКА с единственным заключительным состоянием S и функцией переходов:δ1(H, a) = Xδ1(H, b) = Aδ1(X, b) = Yδ1(X, ⊥) = Sδ1(A, a) = Yδ1(Y, a) = Yδ1(Y, b) = Yδ1(Y,⊥) = SПо ДКА строим грамматику G1, позволяющую воспользоваться алгоритмом детерминированного разбора:G1:S → X⊥ | Y⊥Y → Ya | Yb | Aa | XbX →aA →bВ заключение раздела о регулярных языках приведем пример использования автоматов в решении теоретических задач.Задача.n nДоказать, что контекстно-свободный язык L = { a b | n ≥ 0} нерегулярен.Доказательство (от противного).Предположим, что язык L регулярен.
Тогда существует конечный автомат ( ДКА илиНКА ) A = ( K , Σ, δ , I , F ) , допускающий язык L : L( A) = L . ( Согласно утверждению 10, любой регулярный язык может быть задан конечным автоматом). Пусть число состояний автоk kk kмата A равно k (k > 0). Рассмотрим цепочку a b ∈ L. Так как L =L (A), a b ∈ L (A). Это ознаk kчает, что в автомате A есть успешный путь T с пометкой a b :aaaabbbbp1 ⎯⎯→p2 ⎯⎯→L⎯⎯→pk ⎯⎯→pk +1 ⎯⎯→pk + 2 ⎯⎯→L ⎯⎯→p2 k ⎯⎯→p2 k +1 ,где pi ∈ K для i = 1, K ,2k + 1 . Так как в автомате A всего k состояний, среди p1, p2, …, pk + 1найдутся хотя бы два одинаковых.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
