Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Алгоритм построения КС-грамматики по МП-автомату

Алгоритм построения КС-грамматики по МП-автомату


Дадим сначала неформальную мотивировку той конструкции, которая будет приведена ниже. Будем рассматривать МП-автомат как "игрока", ставящего цели следующего вида: "находясь в состоянии q и имея верхний символ магазина Z, перейти в состояние s". Условимся записывать такую цель в виде тройки [qZs]. Как может наш "игрок" достичь поставленной цели? Если во множестве команд автомата ("правил игры") есть команда


qaZ\to rX_1X_2\ldots X_k,

где для каждого i имеем X_i — магазинный символ (X_i\in \Gamma), то после выполнения этой команды МП-автомат перейдет в состояние r.


Если r=s, то цель достигнута, иначе ставим цель [rX_1s_1], а достигнув ее, ставим цель [s_1X_2s_2] и т.д. Достигнув цели [s_{k-1}X_ks], "игрок" достигает и цели [qZs]. Так как рассматривается допуск с пустым магазином, то символы X_i должны по очереди покинуть магазин, и только в этом случае может быть достигнута "глобальная" цель МП-автомата: [q_0Zq_f],~q_f\in F ("находясь в начальном состоянии и имея верхним символом магазина начальный магазинный символ, попасть в одно из заключительных состояний, опустошив магазин"). Так как, вообще говоря, "игрок" не знает наперед последовательности состояний s_1,s_2,\ldots,s_{k-1}, ведущих к цели, он должен перебрать все такие последовательности.


Эти неформальные соображения лежат в основе следующей конструкции.


Пусть дан МП-автомат M=(Q,V,\Gamma,q_0,F,Z_0,\delta). Определим КС-грамматику G_M=(V,N,S,P), терминальный алфавит которой совпадает со входным алфавитом МП-автомата M, следующим образом.


Нетерминальный алфавит N грамматики есть множество, находящееся во взаимно однозначном соответствии с множеством всех упорядоченных троек вида (q,Z,s), где q,s\in Q,~Z\in\Gamma, пополненное символом S, не принадлежащим ни одному из множеств Q,V,\Gamma и объявляемым аксиомой грамматики. Упорядоченные тройки указанного вида записывают обычно как [qZs], интуитивно понимая каждую такую тройку как охарактеризованную выше цель.


Таким образом, N=\{[qZa]\colon\,q,s\in Q,~Z\in\Gamma\}\cup\{S\}.


Множество правил вывода P грамматики G_M строится так:


а) если команда qaZ\to rX_1X_2\ldots X_k,~k\geqslant1, принадлежит системе команд \delta, то в P записываются все правила вида


[qZs_k]\to a[rX_1s_1][s_1X_2s_2]\ldots [s_{k-1}X_ks_k]

для любой последовательности k состояний s_1,\ldots,s_k множества Q (тем самым к P добавляется |Q|^k правил на каждую команду указанного вида);


б) для каждой команды qaZ\to r\lambda в \delta в P добавляется правило [qZs]\to a;
в) для каждого q_f\in F в P вводится правило S\to[q_0Z_0q_f];
г) никаких других правил в P, кроме определенных пунктов а-в, нет.



Пример 8.17. Для МП-автомата M=(\{q_0,q_1,q_2\}, \{a,b\}, \{a,b,Z\}, q_0, \{q_0\}, Z,\delta) с множеством команд \delta, имеющих вид


\begin{array}{lll}q_0aZ\to q_1aZ,&\quad q_1aa\to q_1aa,&\quad q_1ba\to q_2\lambda,\\ q_2ba\to q_2\lambda,&\quad q_2\lambda Z\to q_0\lambda,&\quad q_0\lambda Z\to q_0\lambda, \end{array}

построим эквивалентную ему КС-грамматику. Можно доказать, что этот МП-автомат допускает язык \{a^nb^n\colon n\geqslant0\}. Заметим, что МП-автомат M допускает пустую цепочку, применяя к начальной конфигурации (q_0,\lambda,Z) последнюю команду. Построенная по данной системе команд грамматика будет иметь следующий вид:


\begin{aligned}&S\to[q_0Zq_0],\\ &[q_0Zs_2]\to a[q_1as_1][s_1Zs_2],~ s_1,s_2\in \{q_0,q_1,q_2\},\\ &[q_1as_2]\to a[q_1as_1][s_1as_2],~ s_1,s_2\in\{q_0,q_1,q_2\},\\ &[q_1aq_2]\to b,\qquad [q_2aq_2]\to b,\\ &[q_2Zq_0]\to\lambda,\qquad [q_0Zq_0]\to\lambda. \end{aligned}

Подчеркнем, что во второй и третьей строчках имеется не по одному, а по 3^2=9 правил (число всех последовательностей двух состояний из трехэлементного множества состояний). Выведем в этой грамматике цепочку aabb:


\begin{aligned}S&\vdash [q_0Zq_0]\vdash a[q_1aq_2][q_2Zq_0]\vdash aa[q_1aq_2] [q_2aq_2][q_2Zq_0]\vdash\\ &\vdash aab[q_2aq_2][q_2Zq_0]\vdash aabb[q_2Zq_0]\vdash aabb. \end{aligned}

На втором шаге этого вывода мы применяем то правило вывода из девяти правил второй строки, которое получается при подстановке вместо s_1 состояния q_2, а вместо s_2 состояния q_0. Мы "угадываем" эти состояния, зная (по системе команд исходного МП-автомата), что достичь заключительного состояния по прочтении (непустой) входной цепочки наш МП-автомат может только из состояния q_2. В то же время, если бы мы на втором шаге использовали правило второй строки, получающееся подстановкой s_1=q_1,~s_2=q_2, возник бы бесполезный нетерминал [q_1aq_1] и наш вывод зашел бы в тупик.


Аналогично на третьем шаге используется то правило из девяти правил третьей строки, в котором s_1=s_2=q_2. После этого применяем по очереди правила четвертой, пятой и шестой строк, завершая вывод.


Если мы теперь в построенном выводе "считаем" по шагам магазинные символы, заключенные в квадратных скобках между состояниями, то получим Z,aZ,aaZ,aZ,Z, т.е. получим изменение содержимого магазина (не считая последнего шага, когда происходит его окончате

льное опустошение), представленное в следующем выводе на множестве конфигураций МП-автомата M\colon
(q_0,aabb,Z)\vdash (q_1,abb,aZ)\vdash (q_1,bb,aaZ)\vdash (q_2,b,aZ)\vdash (q_2,\lambda,Z)\vdash (q_2,\lambda,\lambda).

Этот вывод есть не что иное, как допускающая последовательность конфигураций для цепочки aabb. Читая же последовательности состояний в квадратных скобках, мы получим в итоге ту последовательность состояний, которую проходит МП-автомат, допуская написанную выше цепочку.


Действительно, после первого шага вывода в грамматике получим последовательность q_0,q_0, что можно интерпретировать так: "из состояния q_0 перейти (вернуться) в это же состояние q_0 прочитав входную цепочку".


После второго шага будем иметь q_0,q_1,q_1,q_2,q_2,q_0, что означает: "чтобы вернуться в q_0, сначала нужно попасть в q_2 через q_1").


После третьего шага получим gq_0,q_1,q_2,q_0. Это и есть результирующая последовательность состояний, так как все следующие шаги МП-автомата связаны с "выталкиванием" символов из магазина и не приводят к возникновению новых целей.




Как правило, грамматика, которая указанным выше способом строится по МП-автомату, оказывается очень громоздкой, содержит много бесполезных и недостижимых символов. Это связано с тем, что в ней фигурируют произвольные последовательности состояний МП-автомата фиксированной длины. Что касается разобранного примера 8.17, то в этом случае легко написать грамматику для языка \{a^nb^n\colon n\geqslant0\} непосредственно:


S\to aSb\mid ab\mid \lambda.

По этой грамматике можно построить МП-автомат, используя алгоритм из первой части доказательства основной теоремы, значительно более простой, чем исходный. Его система команд будет иметь следующий вид:


qaS\to qSb\mid qb,\quad qaa\to q\lambda,\quad qbb\to q\lambda,\quad q\lambda S\to q\lambda.

В общем же случае проблема распознавания эквивалентности двух МП-автоматов (в отличие от такой же проблемы для конечных автоматов) не разрешима, и не существует общего алгоритма "упрощения" (в определенном смысле, "минимизации") МП-автомата, хотя, как мы только что видели, в конкретных случаях это вполне возможно.




Теорема 8.7. МП-автомат M эквивалентен грамматике G_M.


Индукцией по длине n вывода в M докажем, что Z\in\Gamma,~(q,x,Z)\vdash^n(r,\lambda,\lambda) для любых q,r\in Q,~x\in V^{\ast} влечет [qZr]\vdash^{\ast}x в G_M.


Если n=1, то есть (q,x,Z)\vdash(r,\lambda,\lambda), то x\in V\cup\{\lambda\}, и в \delta есть команда qZx\to r\lambda, откуда в P есть правило [qZr]\to x, и [qZr]\vdash^{\ast}x.


Пусть доказываемое верно для каждого n\leqslant m-1, где m>1, и пусть (q,x,Z)\vdash^m(r,\lambda,\lambda), причем первый шаг соответствующего вывода имеет вид


(q,x,Z)\vdash(p,y,X_1X_2\ldots X_k), где x=ay для некоторого a\in V\cup\{\lambda\}.

Аналогично доказательству теоремы 8.6 доказывается, что тогда найдутся такие цепочки x_1x_2\ldots x_k и такая последовательность состояний s_1,\ldots,s_{k-1}, что y=x_1x_2\ldots x_k и


\begin{aligned}(p, x_1x_2\ldots x_k, X_1X_2\ldots X_k)&\vdash^{m_1} (s_1, x_2\ldots x_k, X_2\ldots X_k)\vdash^{m_2}\\ &\vdash^{m_2}\ldots\vdash^{m_{k-1}} (s_{k-1}, x_k, X_k)\vdash^{m_k} (r,\lambda,\lambda),\end{aligned}

где для любого i=\overline{1,k} выполняется 0\leqslant m_i\leqslant m-1. Поэтому в силу теоремы 8.5 для любого i=\overline{1,k-1} имеем


(s_{i-1},x_i,X_i)\vdash^{m_i}(s_i,\lambda,\lambda),

где s_0=p, а s_k=r, и, согласно предположению индукции, [s_{i-1}X_is_i]\vdash^{\ast}x_i.


Следовательно, согласно построению грамматики G_M, имеет место выводимость (что и требовалось доказать)


[qZr]\vdash_{G_M} a[pX_is_i][s_iX_2s_2]\ldots [s_{k-1}X_kr]\vdash_{G_M}^{\ast} ax_1x_2\ldots x_k=ay=x,

Пусть цепочка x допускается МП-автоматом M. Тогда (q_0,x,Z)\vdash_{M}^{\ast}(q_f,\lambda,\lambda), где q_f\in F — одно из заключительных состояний МП-автомата M. Согласно только что доказанному, в этом случае для грамматики G_M выполняется [q_0Z_0q_f] \vdash_{G_M}^{\ast}x. Но так как в множестве правил вывода грамматики G_M есть правило S\to[q_0Z_0q_f], то мы получим S\vdash_{G_M} [q_0Z_0q_f]\vdash_{G_M}^{\ast}x, то есть x\in L(G_M). Итак, L(M)\subseteq L(G_M).


Для доказательства обратного включения докажем сначала, что [qZr]\vdash_{G_M}^{\ast}x влечет (q,x,Z)\vdash_{M}^{\ast}(r,\lambda,\lambda) для любых q,r\in Q,~x\in V^{\ast} и Z\in\Gamma. Снова проведем индукцию по длине вывода (в грамматике G_M). При [qZr]\vdash x получаем правило [qZr]\to x в P и, следовательно, команду qxZ\to r\lambda в \delta, то есть (q,x,Z)\vdash (r,\lambda,\lambda). Если же [qZr]\vdash^mx для некоторого m\geqslant1, то x=ay для некоторого a\in V\cup\{\lambda\} и


[qZr]\vdash a[pX_1s_1][s_1X_2s_2]\ldots[s_{k-1}X_kr],

причем для всех i=\overline{1,k}, имеем [s_{i-1}X_is_i]\vdash^{m_i}x_i, где s_0=p,~s_k=r и 1\leqslant m_i\leqslant m-1, так что y=x_1x_2\ldots x_k.


Согласно предположению индукции, тогда для каждого такого i имеем


(s_{i-1},x_i,X_i)\vdash^{\ast}(s_i,\lambda,\lambda).

Но так как указанный выше первый шаг вывода в грамматике возможен только при наличии команды в МП-автомате qaZ\to pX_1X_2\ldots X_k, то


\begin{aligned}(q,x,Z)&\vdash (p,y, X_1X_2\ldots X_k)\vdash^{\ast} (s_1, x_2\ldots x_k, X_2\ldots X_k) \vdash^{\ast}\\ &\vdash^{\ast} (s_{k-1},x_k,X_k)\vdash^{\ast}(r,\lambda,\lambda). \end{aligned}

Если теперь цепочка x порождается грамматикой G, то есть S_{G_M}^{\ast}x, то первый шаг вывода x из S, согласно определению системы правил грамматики G_M, будет иметь вид S\vdash [q_0Z_0q_f] для некоторого q_f\in F, и, следовательно, [q_0Z_0q_f] \vdash_{G_M}^{\ast}x. Тогда в силу только что доказанного (q_0,x,Z_0) \vdash_{M}^{\ast} (q_f,\lambda,\lambda), то есть x\in L(M). Итак, L(G_M)\subseteq L(M), а поскольку обратное включение уже доказано, то L(M)=L(G_M).




Из доказанных теорем 8.6 и 8.7 получаем следующую теорему.


Теорема 8.8. Язык является контекстно-свободным тогда и только тогда, когда он допускается некоторым МП-автоматом.


Замечание 8.10. Существует одна полезная модификация построения МП-автомата по КС-грамматике. Вернемся к примеру 8.16. Можно заметить, что в этом примере правая часть каждого правила грамматики начинается некоторым терминалом. Учет этой особенности позволяет найти другой МП-автомат, который, как нетрудно показать, тоже эквивалентен данной грамматике. Система команд этого автомата имеет следующий вид:


\begin{aligned}&qaS\to qSbS\mid qS,\quad qcS\to q\lambda,\\ &qaa\to q\lambda,\quad qbb\to q\lambda,\quad qcc\to q\lambda.\end{aligned}


Его преимущество в том, что он "видит" первый непрочитанный символ входной цепочки и, следовательно, имеет меньше альтернатив при выборе команды: например, если очередной символ есть b, то ни одна из команд первых двух строк не может быть применена. Тогда этот автомат имеет меньше возможностей попасть в тупик.


В общем случае, если правая часть любого правила грамматики имеет вид a\xi, где a\in V, МП-автомат, эквивалентный данной грамматике, определяется командами вида


qaA\to a\xi,\qquad qbb\to q\lambda,\quad b\in V,

(первая — для правила A\to a\xi). В такой модификации МП-автомат записывает в магазин "хвост" правой части правила, следующей за первым терминалом.


Можно доказать, что любая КС-грамматика может быть определена правилами такого вида (так называемая нормальная форма Грейбах).

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved