И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Язык, допускаемый НКА, — это множество пометок всех успешных путей.Если начальное состояние автомата (НКА или ДКА) одновременно является и заключительным, то автомат допускает пустую цепочку .ЗамечаниеАвтомат, построенный по регулярной грамматике без пустых правых частей, не допускает .Для построения разбора по регулярной грамматике в недетерминированном случаеможно предложить алгоритм, который будет перебирать все возможные варианты сверток(переходов) один за другим; если цепочка принадлежит языку, то будет найден успешныйпуть; если каждый из просмотренных вариантов завершится неудачей, то цепочка языку непринадлежит.

Однако такой алгоритм практически неприемлем, поскольку при переборе вариантов мы, скорее всего, снова окажемся перед проблемой выбора и, следовательно, будемиметь «дерево отложенных вариантов» и экспоненциальный рост сложности разбора.Один из наиболее важных результатов теории конечных автоматов состоит в том,что класс языков, определяемых недетерминированными конечными автоматами, совпадаетс классом языков, определяемых детерминированными конечными автоматами.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  pk pk 1 pk 2  p2k p2k 1 ,где pi  K для i  1, ,2k  1 . Так как в автомате A всего k состояний, среди p1, p2, …, pk  1найдутся хотя бы два одинаковых. Иными словами, существуют i, j, 1  i < j  k, такие что   p j пути T является циклом. Пусть длинаpi  pj. Таким образом, участок pi aaэтого цикла равна m (m  0, так как цикл — это непустой путь). Рассмотрим успешный путьaaT , который отличается от T тем, что циклический участок pi  p j присутствуетв нем дважды:aaaaaabp1  pi  ( pi  p j ) pj  pk 1  p2k 1 .33Элементы теории трансляции / Разбор по регулярным грамматикамПометкой пути T  является цепочкаk m kПоскольку T  — успешный путь,k m kb  L , получаем, что L  L(A) .

Это противоречит равенству L  L(A) . Следовательно, предположение о том, что L регулярен, неверно ab  L(A) . Так как aa k mb k .Регулярные выраженияКроме регулярных грамматик и конечных автоматов, существует еще один широкоиспользуемый в математических теориях и приложениях формализм, задающий регулярныеязыки. Это регулярные выражения. Они позволяют описать любой регулярный язык над заданным алфавитом, используя три вида операций:  (объединение),(итерация). 15) (конкатенация),Определение. Пусть L, L1, L2 — языки над алфавитом .

Характеристики

Список файлов книги