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

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

[cbm]qaZ\to rX_1X_2\ldots X_k,[/cbm]

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

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

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

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

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

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

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

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

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

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

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

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

[cbm]\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}[/cbm]

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

[cbm]\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}[/cbm]

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

[cbm]\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}[/cbm]

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

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

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

льное опустошение), представленное в следующем выводе на множестве конфигураций МП-автомата [cbm]M\colon[/cbm]
[cbm](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).[/cbm]

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

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

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

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


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

[cbm]S\to aSb\mid ab\mid \lambda.[/cbm]

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

[cbm]qaS\to qSb\mid qb,\quad qaa\to q\lambda,\quad qbb\to q\lambda,\quad q\lambda S\to q\lambda.[/cbm]

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


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

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

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

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

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

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

[cbm]\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}[/cbm]

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

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

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

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

[cbm][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,[/cbm]

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

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

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

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

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

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

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

[cbm]\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}[/cbm]

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


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

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

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

[cbm]\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}[/cbm]

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

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

[cbm]qaA\to a\xi,\qquad qbb\to q\lambda,\quad b\in V,[/cbm]

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

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: