Алгоритм построения КС-грамматики по МП-автомату
Дадим сначала неформальную мотивировку той конструкции, которая будет приведена ниже. Будем рассматривать МП-автомат как "игрока", ставящего цели следующего вида: "находясь в состоянии и имея верхний символ магазина , перейти в состояние ". Условимся записывать такую цель в виде тройки . Как может наш "игрок" достичь поставленной цели? Если во множестве команд автомата ("правил игры") есть команда
где для каждого имеем — магазинный символ , то после выполнения этой команды МП-автомат перейдет в состояние .
Если , то цель достигнута, иначе ставим цель , а достигнув ее, ставим цель и т.д. Достигнув цели , "игрок" достигает и цели . Так как рассматривается допуск с пустым магазином, то символы должны по очереди покинуть магазин, и только в этом случае может быть достигнута "глобальная" цель МП-автомата: ("находясь в начальном состоянии и имея верхним символом магазина начальный магазинный символ, попасть в одно из заключительных состояний, опустошив магазин"). Так как, вообще говоря, "игрок" не знает наперед последовательности состояний , ведущих к цели, он должен перебрать все такие последовательности.
Эти неформальные соображения лежат в основе следующей конструкции.
Пусть дан МП-автомат . Определим КС-грамматику , терминальный алфавит которой совпадает со входным алфавитом МП-автомата , следующим образом.
Нетерминальный алфавит грамматики есть множество, находящееся во взаимно однозначном соответствии с множеством всех упорядоченных троек вида , где , пополненное символом , не принадлежащим ни одному из множеств и объявляемым аксиомой грамматики. Упорядоченные тройки указанного вида записывают обычно как , интуитивно понимая каждую такую тройку как охарактеризованную выше цель.
Таким образом, .
Множество правил вывода грамматики строится так:
а) если команда , принадлежит системе команд , то в записываются все правила вида
для любой последовательности состояний множества (тем самым к добавляется правил на каждую команду указанного вида);
б) для каждой команды  в  в  добавляется правило ![[qZs]\to a](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAFYAAAAWBAMAAACoIHaoAAAAMFBMVEVHcEwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAlTPQ5AAAAD3RSTlMAAYHBQtemEFwhkfAxgnIEK5xVAAABjElEQVQoz2NgYBRgQAOMggw4gP8ndBHhzwI41DpBJdiVgEATbK4wTrVQWuLrCpf14RCDCallC2fg2V1AnFrRAobTexjQ1bIXYFPrxsAefwBDLUcDmlqW5M4EhnKG0h8MIHY6slpJQwhdZTQDorb7QLYBkJUPMqO1MAvFvSvAJM8+if8CILUsPxj8LwA99w0UXrGMn1DUFjuAyOoEhq9gtaIbGd4DRfQTGI4wMP5eMQGilk8JDLS+TQBy1h/g/AV2g38CY74AMHwFGHKAov8DIGp574LBLZBaxt0CHD/Aat83MG4GxnU4A3sgAw/P0y+YbuD8xsD2HaLWgecvMB4mMIgtYOxXYPmJ6TfOTwysAZkgtecbSr8wzN4jKGHfwKB6gCkBJS4MwCkkikF/eQBILV+U6QfG/P////9mYChNCitAVssHjgvGo8tehTmAw1dS1ACYaAVByZaxRAAl3jghcSwwkWEmNI7nK6AmYDxph3F9I5FqBRgOGxuh5CGcal0tGBhQM5iUMS61xOdNAHmraW0Ad/LfAAAAAElFTkSuQmCC) ; в) для каждого  в  вводится правило ![S\to[q_0Z_0q_f]](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAHIAAAAYCAMAAAARbFlzAAAAM1BMVEVHcEwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADbQS4qAAAAEHRSTlMAcSAxwNcQAUGB8GGxoZFRg8RiLgAAAitJREFUSMe9ltuSrCAMRbkkEBCQ///aSbg42uqM033q5MHqsiUr7GyiSv0pvPfqgzisfpbLQ4UPmFRrmL9dQERt0u/I28p0GEE/raeJdJidcgnLA+TNP6bGshDpGu2P+5xISH3V+j5SR9dqr1Y9QdrO8tVdlf8MmagTF/UIqceDePUQuCdI19am34gbcq0x2FvFljPSachOr69i5JpfCRlWky+QrEdl6l397hXJbvM2nroWTsSFvZRiurKPywK98SvtpG1ID6Ii1BddlorjjiU3juEiF32FFGFK3XIYOoTG5YBsrfcRjsS1ihyO1c6aQBTwiO1pGkl3yJ7Q44a04RAp6j2SJ5ARlwc5/mUa2sZ2SrRWhjUgbJvMzVItLaW4bEjf9ehyXYR9EdbXWXwInN9NYt+YUQGE5qS3OzWSzmZDUi/D3Bj8ZB9fYRSPrBWsajcCNFcjSCNqBrnYMVUj7XoZqvayCJ4ekoTiFVBOUkIYI4CHL2WxSuJErtNW+UdYa6hh+UaCBgwFi7tGnkeBwZyAiyfZGeQ2S2aweF1YansugLVJqJHMN1LqWbS5mxdXA894aWXL25Dy6ushoNlLvm1mK0M6H5KHr9g58KSVdhP2WGNkIacVZytT+BRporhWLAFn04W8wphMvtS1rUD6ACkZCnAYVfiQxAsLzOnD54uj+Wu8pPw7SCh9n+1aSrGPPnYIRwn4Z+R7n1uWp9Q/+Vp7HgGTUf833PEIfgHTthU6ZPU8rAAAAABJRU5ErkJggg==) ; г) никаких других правил в  , кроме определенных пунктов а-в, нет.
Пример 8.17. Для МП-автомата с множеством команд , имеющих вид
построим эквивалентную ему КС-грамматику. Можно доказать, что этот МП-автомат допускает язык . Заметим, что МП-автомат допускает пустую цепочку, применяя к начальной конфигурации последнюю команду. Построенная по данной системе команд грамматика будет иметь следующий вид:
Подчеркнем, что во второй и третьей строчках имеется не по одному, а по правил (число всех последовательностей двух состояний из трехэлементного множества состояний). Выведем в этой грамматике цепочку 
На втором шаге этого вывода мы применяем то правило вывода из девяти правил второй строки, которое получается при подстановке вместо состояния , а вместо состояния . Мы "угадываем" эти состояния, зная (по системе команд исходного МП-автомата), что достичь заключительного состояния по прочтении (непустой) входной цепочки наш МП-автомат может только из состояния . В то же время, если бы мы на втором шаге использовали правило второй строки, получающееся подстановкой , возник бы бесполезный нетерминал и наш вывод зашел бы в тупик.
Аналогично на третьем шаге используется то правило из девяти правил третьей строки, в котором . После этого применяем по очереди правила четвертой, пятой и шестой строк, завершая вывод.
Если мы теперь в построенном выводе "считаем" по шагам магазинные символы, заключенные в квадратных скобках между состояниями, то получим , т.е. получим изменение содержимого магазина (не считая последнего шага, когда происходит его окончате льное опустошение), представленное в следующем выводе на множестве конфигураций МП-автомата 
Этот вывод есть не что иное, как допускающая последовательность конфигураций для цепочки . Читая же последовательности состояний в квадратных скобках, мы получим в итоге ту последовательность состояний, которую проходит МП-автомат, допуская написанную выше цепочку.
Действительно, после первого шага вывода в грамматике получим последовательность , что можно интерпретировать так: "из состояния перейти (вернуться) в это же состояние прочитав входную цепочку".
После второго шага будем иметь , что означает: "чтобы вернуться в , сначала нужно попасть в через ").
После третьего шага получим g . Это и есть результирующая последовательность состояний, так как все следующие шаги МП-автомата связаны с "выталкиванием" символов из магазина и не приводят к возникновению новых целей.
Как правило, грамматика, которая указанным выше способом строится по МП-автомату, оказывается очень громоздкой, содержит много бесполезных и недостижимых символов. Это связано с тем, что в ней фигурируют произвольные последовательности состояний МП-автомата фиксированной длины. Что касается разобранного примера 8.17, то в этом случае легко написать грамматику для языка непосредственно:
По этой грамматике можно построить МП-автомат, используя алгоритм из первой части доказательства основной теоремы, значительно более простой, чем исходный. Его система команд будет иметь следующий вид:
В общем же случае проблема распознавания эквивалентности двух МП-автоматов (в отличие от такой же проблемы для конечных автоматов) не разрешима, и не существует общего алгоритма "упрощения" (в определенном смысле, "минимизации") МП-автомата, хотя, как мы только что видели, в конкретных случаях это вполне возможно.
Теорема 8.7. МП-автомат эквивалентен грамматике .
Индукцией по длине вывода в докажем, что для любых влечет в .
Если , то есть , то , и в есть команда , откуда в есть правило , и .
Пусть доказываемое верно для каждого , где , и пусть , причем первый шаг соответствующего вывода имеет вид
Аналогично доказательству теоремы 8.6 доказывается, что тогда найдутся такие цепочки и такая последовательность состояний , что и
где для любого выполняется . Поэтому в силу теоремы 8.5 для любого имеем
где , а , и, согласно предположению индукции, .
Следовательно, согласно построению грамматики , имеет место выводимость (что и требовалось доказать)
Пусть цепочка допускается МП-автоматом . Тогда , где — одно из заключительных состояний МП-автомата . Согласно только что доказанному, в этом случае для грамматики выполняется . Но так как в множестве правил вывода грамматики есть правило , то мы получим , то есть . Итак, .
Для доказательства обратного включения докажем сначала, что влечет для любых и . Снова проведем индукцию по длине вывода (в грамматике ). При получаем правило в и, следовательно, команду в , то есть . Если же для некоторого , то для некоторого и
причем для всех , имеем , где и , так что .
Согласно предположению индукции, тогда для каждого такого имеем
Но так как указанный выше первый шаг вывода в грамматике возможен только при наличии команды в МП-автомате , то
Если теперь цепочка порождается грамматикой , то есть , то первый шаг вывода из , согласно определению системы правил грамматики , будет иметь вид для некоторого , и, следовательно, . Тогда в силу только что доказанного , то есть . Итак, , а поскольку обратное включение уже доказано, то .
Из доказанных теорем 8.6 и 8.7 получаем следующую теорему.
Теорема 8.8. Язык является контекстно-свободным тогда и только тогда, когда он допускается некоторым МП-автоматом.
Замечание 8.10. Существует одна полезная модификация построения МП-автомата по КС-грамматике. Вернемся к примеру 8.16. Можно заметить, что в этом примере правая часть каждого правила грамматики начинается некоторым терминалом. Учет этой особенности позволяет найти другой МП-автомат, который, как нетрудно показать, тоже эквивалентен данной грамматике. Система команд этого автомата имеет следующий вид:
Его преимущество в том, что он "видит" первый непрочитанный символ входной цепочки и, следовательно, имеет меньше альтернатив при выборе команды: например, если очередной символ есть , то ни одна из команд первых двух строк не может быть применена. Тогда этот автомат имеет меньше возможностей попасть в тупик.
В общем случае, если правая часть любого правила грамматики имеет вид , где , МП-автомат, эквивалентный данной грамматике, определяется командами вида
(первая — для правила ). В такой модификации МП-автомат записывает в магазин "хвост" правой части правила, следующей за первым терминалом.
Можно доказать, что любая КС-грамматика может быть определена правилами такого вида (так называемая нормальная форма Грейбах).
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|