Алгоритм построения КС-грамматики по МП-автомату
Дадим сначала неформальную мотивировку той конструкции, которая будет приведена ниже. Будем рассматривать МП-автомат как "игрока", ставящего цели следующего вида: "находясь в состоянии [math]q[/math] и имея верхний символ магазина [math]Z[/math], перейти в состояние [math]s[/math]". Условимся записывать такую цель в виде тройки [math][qZs][/math]. Как может наш "игрок" достичь поставленной цели? Если во множестве команд автомата ("правил игры") есть команда
[math]qaZ\to rX_1X_2\ldots X_k,[/math]
где для каждого [math]i[/math] имеем [math]X_i[/math] — магазинный символ [math](X_i\in \Gamma)[/math], то после выполнения этой команды МП-автомат перейдет в состояние [math]r[/math].
Если [math]r=s[/math], то цель достигнута, иначе ставим цель [math][rX_1s_1][/math], а достигнув ее, ставим цель [math][s_1X_2s_2][/math] и т.д. Достигнув цели [math][s_{k-1}X_ks][/math], "игрок" достигает и цели [math][qZs][/math]. Так как рассматривается допуск с пустым магазином, то символы [math]X_i[/math] должны по очереди покинуть магазин, и только в этом случае может быть достигнута "глобальная" цель МП-автомата: [math][q_0Zq_f],~q_f\in F[/math] ("находясь в начальном состоянии и имея верхним символом магазина начальный магазинный символ, попасть в одно из заключительных состояний, опустошив магазин"). Так как, вообще говоря, "игрок" не знает наперед последовательности состояний [math]s_1,s_2,\ldots,s_{k-1}[/math], ведущих к цели, он должен перебрать все такие последовательности.
Эти неформальные соображения лежат в основе следующей конструкции.
Пусть дан МП-автомат [math]M=(Q,V,\Gamma,q_0,F,Z_0,\delta)[/math]. Определим КС-грамматику [math]G_M=(V,N,S,P)[/math], терминальный алфавит которой совпадает со входным алфавитом МП-автомата [math]M[/math], следующим образом.
Нетерминальный алфавит [math]N[/math] грамматики есть множество, находящееся во взаимно однозначном соответствии с множеством всех упорядоченных троек вида [math](q,Z,s)[/math], где [math]q,s\in Q,~Z\in\Gamma[/math], пополненное символом [math]S[/math], не принадлежащим ни одному из множеств [math]Q,V,\Gamma[/math] и объявляемым аксиомой грамматики. Упорядоченные тройки указанного вида записывают обычно как [math][qZs][/math], интуитивно понимая каждую такую тройку как охарактеризованную выше цель.
Таким образом, [math]N=\{[qZa]\colon\,q,s\in Q,~Z\in\Gamma\}\cup\{S\}[/math].
Множество правил вывода [math]P[/math] грамматики [math]G_M[/math] строится так:
а) если команда [math]qaZ\to rX_1X_2\ldots X_k,~k\geqslant1[/math], принадлежит системе команд [math]\delta[/math], то в [math]P[/math] записываются все правила вида
[math][qZs_k]\to a[rX_1s_1][s_1X_2s_2]\ldots [s_{k-1}X_ks_k][/math]
для любой последовательности [math]k[/math] состояний [math]s_1,\ldots,s_k[/math] множества [math]Q[/math] (тем самым к [math]P[/math] добавляется [math]|Q|^k[/math] правил на каждую команду указанного вида);
б) для каждой команды [math]qaZ\to r\lambda[/math] в [math]\delta[/math] в [math]P[/math] добавляется правило [math][qZs]\to a[/math];
в) для каждого [math]q_f\in F[/math] в [math]P[/math] вводится правило [math]S\to[q_0Z_0q_f][/math];
г) никаких других правил в [math]P[/math], кроме определенных пунктов а-в, нет.
Пример 8.17. Для МП-автомата [math]M=(\{q_0,q_1,q_2\}, \{a,b\}, \{a,b,Z\}, q_0, \{q_0\}, Z,\delta)[/math] с множеством команд [math]\delta[/math], имеющих вид
[math]\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}[/math]
построим эквивалентную ему КС-грамматику. Можно доказать, что этот МП-автомат допускает язык [math]\{a^b^n\colon n\geqslant0\}[/math]. Заметим, что МП-автомат [math]M[/math] допускает пустую цепочку, применяя к начальной конфигурации [math](q_0,\lambda,Z)[/math] последнюю команду. Построенная по данной системе команд грамматика будет иметь следующий вид:
[math]\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}[/math]
Подчеркнем, что во второй и третьей строчках имеется не по одному, а по [math]3^2=9[/math] правил (число всех последовательностей двух состояний из трехэлементного множества состояний). Выведем в этой грамматике цепочку [math]aabb:[/math]
[math]\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}[/math]
На втором шаге этого вывода мы применяем то правило вывода из девяти правил второй строки, которое получается при подстановке вместо [math]s_1[/math] состояния [math]q_2[/math], а вместо [math]s_2[/math] состояния [math]q_0[/math]. Мы "угадываем" эти состояния, зная (по системе команд исходного МП-автомата), что достичь заключительного состояния по прочтении (непустой) входной цепочки наш МП-автомат может только из состояния [math]q_2[/math]. В то же время, если бы мы на втором шаге использовали правило второй строки, получающееся подстановкой [math]s_1=q_1,~s_2=q_2[/math], возник бы бесполезный нетерминал [math][q_1aq_1][/math] и наш вывод зашел бы в тупик.
Аналогично на третьем шаге используется то правило из девяти правил третьей строки, в котором [math]s_1=s_2=q_2[/math]. После этого применяем по очереди правила четвертой, пятой и шестой строк, завершая вывод.
Если мы теперь в построенном выводе "считаем" по шагам магазинные символы, заключенные в квадратных скобках между состояниями, то получим [math]Z,aZ,aaZ,aZ,Z[/math], т.е. получим изменение содержимого магазина (не считая последнего шага, когда происходит его окончате льное опустошение), представленное в следующем выводе на множестве конфигураций МП-автомата [math]M\colon[/math]
[math](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).[/math]
Этот вывод есть не что иное, как допускающая последовательность конфигураций для цепочки [math]aabb[/math]. Читая же последовательности состояний в квадратных скобках, мы получим в итоге ту последовательность состояний, которую проходит МП-автомат, допуская написанную выше цепочку.
Действительно, после первого шага вывода в грамматике получим последовательность [math]q_0,q_0[/math], что можно интерпретировать так: "из состояния [math]q_0[/math] перейти (вернуться) в это же состояние [math]q_0[/math] прочитав входную цепочку".
После второго шага будем иметь [math]q_0,q_1,q_1,q_2,q_2,q_0[/math], что означает: "чтобы вернуться в [math]q_0[/math], сначала нужно попасть в [math]q_2[/math] через [math]q_1[/math]").
После третьего шага получим g[math]q_0,q_1,q_2,q_0[/math]. Это и есть результирующая последовательность состояний, так как все следующие шаги МП-автомата связаны с "выталкиванием" символов из магазина и не приводят к возникновению новых целей.
Как правило, грамматика, которая указанным выше способом строится по МП-автомату, оказывается очень громоздкой, содержит много бесполезных и недостижимых символов. Это связано с тем, что в ней фигурируют произвольные последовательности состояний МП-автомата фиксированной длины. Что касается разобранного примера 8.17, то в этом случае легко написать грамматику для языка [math]\{a^b^n\colon n\geqslant0\}[/math] непосредственно:
[math]S\to aSb\mid ab\mid \lambda.[/math]
По этой грамматике можно построить МП-автомат, используя алгоритм из первой части доказательства основной теоремы, значительно более простой, чем исходный. Его система команд будет иметь следующий вид:
[math]qaS\to qSb\mid qb,\quad qaa\to q\lambda,\quad qbb\to q\lambda,\quad q\lambda S\to q\lambda.[/math]
В общем же случае проблема распознавания эквивалентности двух МП-автоматов (в отличие от такой же проблемы для конечных автоматов) не разрешима, и не существует общего алгоритма "упрощения" (в определенном смысле, "минимизации") МП-автомата, хотя, как мы только что видели, в конкретных случаях это вполне возможно.
Теорема 8.7. МП-автомат [math]M[/math] эквивалентен грамматике [math]G_M[/math].
Индукцией по длине [math]n[/math] вывода в [math]M[/math] докажем, что [math]Z\in\Gamma,~(q,x,Z)\vdash^n(r,\lambda,\lambda)[/math] для любых [math]q,r\in Q,~x\in V^{\ast}[/math] влечет [math][qZr]\vdash^{\ast}x[/math] в [math]G_M[/math].
Если [math]n=1[/math], то есть [math](q,x,Z)\vdash(r,\lambda,\lambda)[/math], то [math]x\in V\cup\{\lambda\}[/math], и в [math]\delta[/math] есть команда [math]qZx\to r\lambda[/math], откуда в [math]P[/math] есть правило [math][qZr]\to x[/math], и [math][qZr]\vdash^{\ast}x[/math].
Пусть доказываемое верно для каждого [math]n\leqslant m-1[/math], где [math]m>1[/math], и пусть [math](q,x,Z)\vdash^m(r,\lambda,\lambda)[/math], причем первый шаг соответствующего вывода имеет вид
[math](q,x,Z)\vdash(p,y,X_1X_2\ldots X_k)[/math], где [math]x=ay[/math] для некоторого [math]a\in V\cup\{\lambda\}[/math].
Аналогично доказательству теоремы 8.6 доказывается, что тогда найдутся такие цепочки [math]x_1x_2\ldots x_k[/math] и такая последовательность состояний [math]s_1,\ldots,s_{k-1}[/math], что [math]y=x_1x_2\ldots x_k[/math] и
[math]\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}[/math]
где для любого [math]i=\overline{1,k}[/math] выполняется [math]0\leqslant m_i\leqslant m-1[/math]. Поэтому в силу теоремы 8.5 для любого [math]i=\overline{1,k-1}[/math] имеем
[math](s_{i-1},x_i,X_i)\vdash^{m_i}(s_i,\lambda,\lambda),[/math]
где [math]s_0=p[/math], а [math]s_k=r[/math], и, согласно предположению индукции, [math][s_{i-1}X_is_i]\vdash^{\ast}x_i[/math].
Следовательно, согласно построению грамматики [math]G_M[/math], имеет место выводимость (что и требовалось доказать)
[math][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,[/math]
Пусть цепочка [math]x[/math] допускается МП-автоматом [math]M[/math]. Тогда [math](q_0,x,Z)\vdash_{M}^{\ast}(q_f,\lambda,\lambda)[/math], где [math]q_f\in F[/math] — одно из заключительных состояний МП-автомата [math]M[/math]. Согласно только что доказанному, в этом случае для грамматики [math]G_M[/math] выполняется [math][q_0Z_0q_f] \vdash_{G_M}^{\ast}x[/math]. Но так как в множестве правил вывода грамматики [math]G_M[/math] есть правило [math]S\to[q_0Z_0q_f][/math], то мы получим [math]S\vdash_{G_M} [q_0Z_0q_f]\vdash_{G_M}^{\ast}x[/math], то есть [math]x\in L(G_M)[/math]. Итак, [math]L(M)\subseteq L(G_M)[/math].
Для доказательства обратного включения докажем сначала, что [math][qZr]\vdash_{G_M}^{\ast}x[/math] влечет [math](q,x,Z)\vdash_{M}^{\ast}(r,\lambda,\lambda)[/math] для любых [math]q,r\in Q,~x\in V^{\ast}[/math] и [math]Z\in\Gamma[/math]. Снова проведем индукцию по длине вывода (в грамматике [math]G_M[/math]). При [math][qZr]\vdash x[/math] получаем правило [math][qZr]\to x[/math] в [math]P[/math] и, следовательно, команду [math]qxZ\to r\lambda[/math] в [math]\delta[/math], то есть [math](q,x,Z)\vdash (r,\lambda,\lambda)[/math]. Если же [math][qZr]\vdash^mx[/math] для некоторого [math]m\geqslant1[/math], то [math]x=ay[/math] для некоторого [math]a\in V\cup\{\lambda\}[/math] и
[math][qZr]\vdash a[pX_1s_1][s_1X_2s_2]\ldots[s_{k-1}X_kr],[/math]
причем для всех [math]i=\overline{1,k}[/math], имеем [math][s_{i-1}X_is_i]\vdash^{m_i}x_i[/math], где [math]s_0=p,~s_k=r[/math] и [math]1\leqslant m_i\leqslant m-1[/math], так что [math]y=x_1x_2\ldots x_k[/math].
Согласно предположению индукции, тогда для каждого такого [math]i[/math] имеем
[math](s_{i-1},x_i,X_i)\vdash^{\ast}(s_i,\lambda,\lambda).[/math]
Но так как указанный выше первый шаг вывода в грамматике возможен только при наличии команды в МП-автомате [math]qaZ\to pX_1X_2\ldots X_k[/math], то
[math]\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}[/math]
Если теперь цепочка [math]x[/math] порождается грамматикой [math]G[/math], то есть [math]S_{G_M}^{\ast}x[/math], то первый шаг вывода [math]x[/math] из [math]S[/math], согласно определению системы правил грамматики [math]G_M[/math], будет иметь вид [math]S\vdash [q_0Z_0q_f][/math] для некоторого [math]q_f\in F[/math], и, следовательно, [math][q_0Z_0q_f] \vdash_{G_M}^{\ast}x[/math]. Тогда в силу только что доказанного [math](q_0,x,Z_0) \vdash_{M}^{\ast} (q_f,\lambda,\lambda)[/math], то есть [math]x\in L(M)[/math]. Итак, [math]L(G_M)\subseteq L(M)[/math], а поскольку обратное включение уже доказано, то [math]L(M)=L(G_M)[/math].
Из доказанных теорем 8.6 и 8.7 получаем следующую теорему.
Теорема 8.8. Язык является контекстно-свободным тогда и только тогда, когда он допускается некоторым МП-автоматом.
Замечание 8.10. Существует одна полезная модификация построения МП-автомата по КС-грамматике. Вернемся к примеру 8.16. Можно заметить, что в этом примере правая часть каждого правила грамматики начинается некоторым терминалом. Учет этой особенности позволяет найти другой МП-автомат, который, как нетрудно показать, тоже эквивалентен данной грамматике. Система команд этого автомата имеет следующий вид:
[math]\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}[/math]
Его преимущество в том, что он "видит" первый непрочитанный символ входной цепочки и, следовательно, имеет меньше альтернатив при выборе команды: например, если очередной символ есть [math]b[/math], то ни одна из команд первых двух строк не может быть применена. Тогда этот автомат имеет меньше возможностей попасть в тупик.
В общем случае, если правая часть любого правила грамматики имеет вид [math]a\xi[/math], где [math]a\in V[/math], МП-автомат, эквивалентный данной грамматике, определяется командами вида
[math]qaA\to a\xi,\qquad qbb\to q\lambda,\quad b\in V,[/math]
(первая — для правила [math]A\to a\xi[/math]). В такой модификации МП-автомат записывает в магазин "хвост" правой части правила, следующей за первым терминалом.
Можно доказать, что любая КС-грамматика может быть определена правилами такого вида (так называемая нормальная форма Грейбах).
|
Вход
Регистрация
Альбомы
FAQ
Поиск