formal_languages_translation_theory (Формальные грамматики), страница 7

Прианализе данной цепочки получим следующую последовательность переходов в ДС:abbaHACBCSВспомним, что каждый переход в ДС означает свертку сентенциальной формы путем заменыв ней пары «нетерминал-терминал» Nt на нетерминал L, где L → Nt правило вывода в грамматике. Такое применение правила в обратную сторону будем записывать с помощью обратной стрелки Nt ← L (обращение правила вывода). Тогда получим следующую последовательность сверток, соответствующую переходам в ДС:abba  Abba  Cba  Ba  C  SЭта последовательность не что иное, как обращение (правого) вывода цепочки abba в грамматике G. Она соответствует построению дерева снизу вверх (см.

рис. 5).SSSAabbaaCAbbaSabbSSCBAaCBCBCAbbaaaCAbbaabbaРис. 5. Построение дерева вывода снизу вверх.Разбор по праволинейной грамматикеПо диаграмме состояний (см. рис. 4) построим праволинейную автоматную грамматику Gright следующим способом: нетерминалами будут состояния из ДС (кроме S ); каждой дуге из состояния V в заключительное состояние S (помеченной признакомконца ) будет соответствовать правило V → ; каждой дуге из состояния V в состояние W, помеченной символом t, будет соответствовать правило V → tW;14) начальное состояние H объявляется начальным символом грамматики .14)Нетрудно описать и обратный алгоритм для праволинейной автоматной грамматики, если все ее правила содносимвольной правой частью имеют вид V → .

Состояниями ДС будут нетерминалы грамматики и ещеодно специальное заключительное состояние S, в которое для каждого правила вида V →  проводится дуга27Элементы теории трансляции / Разбор по регулярным грамматикамGright   {a, b, }, {H, A, B, C}, P, H P:H → aA | bBA → bCC → bB | aA | B → aCЗаметим, что L(Gright)  L(Gleft), так как грамматики Gright и Gleft соответствуют одной и тойже ДС (см. рис.

4).Рассмотрим разбор цепочки abba по праволинейной грамматике Gright. Последовательность переходов в ДС для этой цепочки такова:abbaHACBCSКаждый переход, за исключением последнего, означает теперь замену в сентенциальнойформе нетерминала на пару «терминал-нетерминал» с помощью некоторого правила выводаграмматики Gright.

В результате получаем следующий (левый) вывод, который соответствуетпоследовательности переходов в ДС:H  aA  abC  abbB  abbaC  abbaТакой вывод отражает построение дерева вывода сверху вниз (см. рис. 6).HHHAACabbaaHbbaaHACCBBCabbaaaACBbHAbbbaCabbaРис. 6. Построение дерева вывода сверху вниз.О недетерминированном разбореПри анализе по леволинейной грамматике может оказаться, что несколько нетерминалов имеют одинаковые правые части, и поэтому неясно, к какому из них делать свертку (см.ситуацию 4 в описании алгоритма). При анализе по праволинейной грамматике может ока-из V, помеченная признаком конца .

Для каждого правила вида V → t W проводится дуга из V в W, помеченная символом t. Начальным состоянием в ДС будет начальный символ H.28Элементы теории трансляции / Разбор по регулярным грамматикамзаться, что нетерминал имеет две правые части с одинаковыми терминальными символами ипоэтому неясно, на какую альтернативу заменить нетерминал. В терминах диаграммы состояний эти ситуации означают, что из одного состояния выходит несколько дуг, ведущих вразные состояния, но помеченных одним и тем же символом.Например, для грамматики G  {a, b, }, {S, A, B}, P, S , гдеP:S → AA → a | BbB → b | Bbразбор будет недетерминированным (т.к.

у нетерминалов 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.