Алгоритм построения КС-грамматики по МП-автомату
Дадим сначала неформальную мотивировку той конструкции, которая будет приведена ниже. Будем рассматривать МП-автомат как "игрока", ставящего цели следующего вида: "находясь в состоянии и имея верхний символ магазина , перейти в состояние ". Условимся записывать такую цель в виде тройки . Как может наш "игрок" достичь поставленной цели? Если во множестве команд автомата ("правил игры") есть команда
где для каждого имеем — магазинный символ , то после выполнения этой команды МП-автомат перейдет в состояние .
Если , то цель достигнута, иначе ставим цель , а достигнув ее, ставим цель и т.д. Достигнув цели , "игрок" достигает и цели . Так как рассматривается допуск с пустым магазином, то символы должны по очереди покинуть магазин, и только в этом случае может быть достигнута "глобальная" цель МП-автомата: ("находясь в начальном состоянии и имея верхним символом магазина начальный магазинный символ, попасть в одно из заключительных состояний, опустошив магазин"). Так как, вообще говоря, "игрок" не знает наперед последовательности состояний , ведущих к цели, он должен перебрать все такие последовательности.
Эти неформальные соображения лежат в основе следующей конструкции.
Пусть дан МП-автомат . Определим КС-грамматику , терминальный алфавит которой совпадает со входным алфавитом МП-автомата , следующим образом.
Нетерминальный алфавит грамматики есть множество, находящееся во взаимно однозначном соответствии с множеством всех упорядоченных троек вида , где , пополненное символом , не принадлежащим ни одному из множеств и объявляемым аксиомой грамматики. Упорядоченные тройки указанного вида записывают обычно как , интуитивно понимая каждую такую тройку как охарактеризованную выше цель.
Таким образом, .
Множество правил вывода грамматики строится так:
а) если команда , принадлежит системе команд , то в записываются все правила вида
для любой последовательности состояний множества (тем самым к добавляется правил на каждую команду указанного вида);
б) для каждой команды в в добавляется правило ; в) для каждого в вводится правило ; г) никаких других правил в , кроме определенных пунктов а-в, нет.
Пример 8.17. Для МП-автомата с множеством команд , имеющих вид
построим эквивалентную ему КС-грамматику. Можно доказать, что этот МП-автомат допускает язык . Заметим, что МП-автомат допускает пустую цепочку, применяя к начальной конфигурации последнюю команду. Построенная по данной системе команд грамматика будет иметь следующий вид:
Подчеркнем, что во второй и третьей строчках имеется не по одному, а по правил (число всех последовательностей двух состояний из трехэлементного множества состояний). Выведем в этой грамматике цепочку
На втором шаге этого вывода мы применяем то правило вывода из девяти правил второй строки, которое получается при подстановке вместо состояния , а вместо состояния . Мы "угадываем" эти состояния, зная (по системе команд исходного МП-автомата), что достичь заключительного состояния по прочтении (непустой) входной цепочки наш МП-автомат может только из состояния . В то же время, если бы мы на втором шаге использовали правило второй строки, получающееся подстановкой , возник бы бесполезный нетерминал и наш вывод зашел бы в тупик.
Аналогично на третьем шаге используется то правило из девяти правил третьей строки, в котором . После этого применяем по очереди правила четвертой, пятой и шестой строк, завершая вывод.
Если мы теперь в построенном выводе "считаем" по шагам магазинные символы, заключенные в квадратных скобках между состояниями, то получим , т.е. получим изменение содержимого магазина (не считая последнего шага, когда происходит его окончате льное опустошение), представленное в следующем выводе на множестве конфигураций МП-автомата
Этот вывод есть не что иное, как допускающая последовательность конфигураций для цепочки . Читая же последовательности состояний в квадратных скобках, мы получим в итоге ту последовательность состояний, которую проходит МП-автомат, допуская написанную выше цепочку.
Действительно, после первого шага вывода в грамматике получим последовательность , что можно интерпретировать так: "из состояния перейти (вернуться) в это же состояние прочитав входную цепочку".
После второго шага будем иметь , что означает: "чтобы вернуться в , сначала нужно попасть в через ").
После третьего шага получим g. Это и есть результирующая последовательность состояний, так как все следующие шаги МП-автомата связаны с "выталкиванием" символов из магазина и не приводят к возникновению новых целей.
Как правило, грамматика, которая указанным выше способом строится по МП-автомату, оказывается очень громоздкой, содержит много бесполезных и недостижимых символов. Это связано с тем, что в ней фигурируют произвольные последовательности состояний МП-автомата фиксированной длины. Что касается разобранного примера 8.17, то в этом случае легко написать грамматику для языка непосредственно:
По этой грамматике можно построить МП-автомат, используя алгоритм из первой части доказательства основной теоремы, значительно более простой, чем исходный. Его система команд будет иметь следующий вид:
В общем же случае проблема распознавания эквивалентности двух МП-автоматов (в отличие от такой же проблемы для конечных автоматов) не разрешима, и не существует общего алгоритма "упрощения" (в определенном смысле, "минимизации") МП-автомата, хотя, как мы только что видели, в конкретных случаях это вполне возможно.
Теорема 8.7. МП-автомат эквивалентен грамматике .
Индукцией по длине вывода в докажем, что для любых влечет в .
Если , то есть , то , и в есть команда , откуда в есть правило , и .
Пусть доказываемое верно для каждого , где , и пусть , причем первый шаг соответствующего вывода имеет вид
Аналогично доказательству теоремы 8.6 доказывается, что тогда найдутся такие цепочки и такая последовательность состояний , что и
где для любого выполняется . Поэтому в силу теоремы 8.5 для любого имеем
где , а , и, согласно предположению индукции, .
Следовательно, согласно построению грамматики , имеет место выводимость (что и требовалось доказать)
Пусть цепочка допускается МП-автоматом . Тогда , где — одно из заключительных состояний МП-автомата . Согласно только что доказанному, в этом случае для грамматики выполняется . Но так как в множестве правил вывода грамматики есть правило , то мы получим , то есть . Итак, .
Для доказательства обратного включения докажем сначала, что влечет для любых и . Снова проведем индукцию по длине вывода (в грамматике ). При получаем правило в и, следовательно, команду в , то есть . Если же для некоторого , то для некоторого и
причем для всех , имеем , где и , так что .
Согласно предположению индукции, тогда для каждого такого имеем
Но так как указанный выше первый шаг вывода в грамматике возможен только при наличии команды в МП-автомате , то
Если теперь цепочка порождается грамматикой , то есть , то первый шаг вывода из , согласно определению системы правил грамматики , будет иметь вид для некоторого , и, следовательно, . Тогда в силу только что доказанного , то есть . Итак, , а поскольку обратное включение уже доказано, то .
Из доказанных теорем 8.6 и 8.7 получаем следующую теорему.
Теорема 8.8. Язык является контекстно-свободным тогда и только тогда, когда он допускается некоторым МП-автоматом.
Замечание 8.10. Существует одна полезная модификация построения МП-автомата по КС-грамматике. Вернемся к примеру 8.16. Можно заметить, что в этом примере правая часть каждого правила грамматики начинается некоторым терминалом. Учет этой особенности позволяет найти другой МП-автомат, который, как нетрудно показать, тоже эквивалентен данной грамматике. Система команд этого автомата имеет следующий вид:
Его преимущество в том, что он "видит" первый непрочитанный символ входной цепочки и, следовательно, имеет меньше альтернатив при выборе команды: например, если очередной символ есть , то ни одна из команд первых двух строк не может быть применена. Тогда этот автомат имеет меньше возможностей попасть в тупик.
В общем случае, если правая часть любого правила грамматики имеет вид , где , МП-автомат, эквивалентный данной грамматике, определяется командами вида
(первая — для правила ). В такой модификации МП-автомат записывает в магазин "хвост" правой части правила, следующей за первым терминалом.
Можно доказать, что любая КС-грамматика может быть определена правилами такого вида (так называемая нормальная форма Грейбах).
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|