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

МП-автомат [cbm]M[/cbm] называют эквивалентным К С-грамматике [cbm]G[/cbm] , если язык, допускаемый [cbm]M[/cbm] , совпадает с языком, порождаемым грамматикой [cbm]G[/cbm] , т.е. если [cbm]L(M) =L(G)[/cbm] .

Опишем алгоритм построения по заданной КС-грамматике эквивалентного ей МП-автомата, а также алгоритм построения по заданному МП-автомату КС-грамматики, которой он эквивалентен.

Для исходной КС-грамматики [cbm]G=(V,N,S,P)[/cbm] определим МП-автомат [cbm]M_G=(\{q\},V,V\cup N,q,\{q\},S,\delts)[/cbm] (с единственным состоянием [cbm]q[/cbm] ), система команд [cbm]\delta[/cbm] которого строится следующим образом: для каждого правила [cbm]A\to\alpha[/cbm] , принадлежащего [cbm]P[/cbm] , в [cbm]\delta[/cbm] записывается команда [cbm]q\lambda A\to q\alpha[/cbm] и для каждого [cbm]a\in V[/cbm] — команда [cbm]qaa\to q\lambda[/cbm] . Никаких других команд в системе команд [cbm]\delta[/cbm] нет.

Пример 8.16. Пусть дана грамматика [cbm]G=(\{a,b,c\},\{S\},S,P)[/cbm] , множество правил вывода [cbm]P[/cbm] которой есть [cbm]S\to aSbS\mid aS\mid c[/cbm] .

Тогда эквивалентный ей МП-автомат задается следующей системой команд:

[cbm]q\lambda S\to qaSbS\mid qaS\mid qc,\qquad qaa\to q\lambda,\qquad qbb\to q\lambda,\qquad qcc\to q\lambda[/cbm]

(мы использовали сокращенную запись нескольких команд с одинаковыми левыми частями по аналогии с тем, как мы это делаем при записи множества правил вывода грамматики).

В системе команд МП-автомата, который строится по заданной КС-грамматике так, как это описано выше, мы видим два "сорта" команд:

1) команды, "моделирующие" применение правил, исходной грамматики (в данном примере это команды первой строки); при выполнении каждой такой команды МП-автомат делает λ-такт, т.е. не продвигает головку по входной ленте;

2) команды "сравнения", согласно которым МП-автомат должен убирать верхний символ магазина всякий раз, когда он совпадает с обозреваемым символом на ленте.

Тогда, читая входную цепочку, такой МП-автомат "моделирует" левый вывод этой цепочки в исходной грамматике, применяя каждый раз, когда верхним символом магазина оказывается нетерминал, команду "первого сорта" и всякий раз, когда верхним символом магазина оказывается терминал исходной грамматики, "команду сравнения".

Прочитаем цепочку [cbm]aacbc:[/cbm]

[cbm]\begin{aligned}(q,aacbc,S)&\vdash (q,aacbc,aSbS)\vdash (q,acbc,SbS)\vdash (q,acbc,aSbS)\vdash (q,cbc,SbS)\vdash\\ &\vdash (q,cbc,cbS)\vdash (q,bc,bS)\vdash (q,c,S)\vdash (q,c,c)\vdash (q,\lambda,\lambda).\end{aligned}[/cbm]

Нетрудно видеть, что этот вывод "моделирует" левый вывод в грамматике:

[cbm]S\vdash aSbS\vdash aaSbS\vdash aacbS\vdash aacbc,[/cbm]

т.е. МП-автомат, строя допускающую последовательность конфигураций для входной цепочки, на каждом шаге, когда верхний символ магазина не совпадает с очередным символом входной цепочки, должен "угадать" применяемое правило (выбрать в данном примере одну из трех первых команд). Неправильный выбор приведет к тупику, например:
[cbm](q,aacbc,S)\vdash (q,aacbc,aS)\vdash (q,acbc,S)\vdash (q,acbc,c).[/cbm]

Докажем, что рассмотренный алгоритм дает МП-автомат, эквивалентный исходной КС-грамматике.

Теорема 8.6. МП-автомат [cbm]M_G[/cbm] эквивалентен КС-грамматике [cbm]G[/cbm] .

Индукцией по длине [cbm]n[/cbm] вывода терминальной цепочки [cbm]x[/cbm] из нетерминала [cbm]A[/cbm] докажем, что если [cbm]A\vdash_{G}^{\ast}x[/cbm] , то

[cbm](q,x,A)\vdash_{M_G}^{\ast}(q,\lambda,\lambda).[/cbm]

Пусть [cbm]n=1[/cbm] , то есть [cbm]A\vdash^{1}x[/cbm] ; тогда в [cbm]P[/cbm] есть правило [cbm]A\to x[/cbm] и, следовательно, в [cbm]\delta[/cbm] есть команда [cbm]q\lambda A\to qx[/cbm] . В таком случае при [cbm]x=\lambda[/cbm] имеет место выводимость [cbm](q,\lambda,A)\vdash(q,\lambda,\lambda)[/cbm] и требуемый вывод на множестве конфигураций МП-автомата [cbm]M_G[/cbm] построен. Если же цепочка [cbm]x[/cbm] непустая, то тогда, расписывая ее по символам, т.е. полагая [cbm]x=x(1)\ldots x(k),~k\geqslant1[/cbm] , получим

[cbm]\bigl(q,x(1)\ldots x(k),A\bigr)\vdash \bigl(q,x(1)\ldots x(k),x(1)\ldots x(k)\bigr).[/cbm]

Из последней конфигурации за [cbm]k[/cbm] шагов посредством применения команд вида [cbm]qaa\to q\lambda[/cbm] , где [cbm]a\in V[/cbm] , выводится конфигурация [cbm](q,\lambda,\lambda)[/cbm] , и, таким образом, [cbm](q,x,A)\vdash^{|x|+1}(q,\lambda,\lambda)[/cbm] .

Пусть теперь доказываемое верно для любого [cbm]n[/cbm] , не превосходящего некоторого [cbm]m-1[/cbm] для [cbm]m\geqslant2[/cbm] , пусть [cbm]A\vdash^mx[/cbm] и первый шаг вывода длины [cbm]m[/cbm] цепочки [cbm]x[/cbm] из нетерминала [cbm]A[/cbm] имеет вид [cbm]A\vdash X_1X_2\ldots X_k[/cbm] , где [cbm]k\geqslant1[/cbm] и для каждого [cbm]i=\overline{1,k}[/cbm] символ [cbm]X_i[/cbm] есть символ объединенного алфавита грамматики*. Далее, из цепочки [cbm]X_1X_2\ldots X_k[/cbm] должна быть выведена терминальная цепочка [cbm]x[/cbm] . Это значит, что для каждого [cbm]i=\overline{1,k}[/cbm] из символа [cbm]X_i[/cbm] выводится какая-то подцепочка цепочки [cbm]x[/cbm] (в частности, если этот символ является терминалом, он будет одним из символов цепочки [cbm]x[/cbm] ). Таким образом, для каждого [cbm]i=\overline{1,k}[/cbm] выполняется [cbm]X_i\vdash^{m_i}x_i[/cbm] , и [cbm]x=x_1x_2\ldots x_k[/cbm] .

*Цепочка [cbm]X_1X_2\ldots X_k[/cbm] не может быть пустой, так как тоща она окажется последней цепочкой рассматриваемого вывода и его длина будет равна 1, а мы предположили, что его длина равна [cbm]m\geqslant1[/cbm] .

Для [cbm]X_i\in N[/cbm] длина вывода га» подцепочки [cbm]m_i[/cbm] не может превышать [cbm]m-1[/cbm] . Следовательно, согласно предположению индукции, имеем

[cbm](q,x_i,X_i)\vdash^{\ast}(q,\lambda,\lambda),[/cbm]

а для [cbm]X_i\in V[/cbm] ( [cbm]m_i=0[/cbm] и, следовательно, [cbm]X_i=x_i[/cbm] ), согласно построению МП-автомата [cbm]M_G[/cbm] , [cbm](q,x_i,x_i)\vdash^{\ast}(q,\lambda,\lambda)[/cbm] . Тогда в силу теоремы 8.5

[cbm](q,x_1x_2\ldots x_k,X_1X_2\ldots X_k)\vdash^{\ast} (q,x_2\ldots x_k,X_2\ldots X_k)\vdash^{\ast} (q,x_k,X_k)\vdash (q,\lambda,\lambda).[/cbm]

Кроме того, так как [cbm]A\vdash X_1X_2\ldots X_k[/cbm] , то в [cbm]P[/cbm] есть правило вывода [cbm]A\to X_1X_2\ldots X_k[/cbm] откуда, согласно построению МП-автомата [cbm]M_G[/cbm] , в [cbm]\delta[/cbm] есть команда

[cbm]q\lambda A\to qX_1X_2\ldots X_k[/cbm] и [cbm](q,x,A)\vdash (q,x, X_1X_2\ldots X_k)[/cbm] , а окончательно [cbm](q,x,A)\vdash^{\ast}(q,\lambda,\lambda)[/cbm] .

Следовательно, если [cbm]x\in L(G)[/cbm] , то [cbm]S\vdash^{\ast}x[/cbm] и [cbm](q,x,S)\vdash^{\ast}(q,\lambda,\lambda)[/cbm] , то есть [cbm]x\in L(M_G)[/cbm] .

Итак, мы доказали, что [cbm]L(G)\subseteq L(M_G)[/cbm] .

Чтобы доказать обратное включение, сначала индукцией по длине п вывода на множестве конфигураций МП-автомата [cbm]M_G[/cbm] докажем, что [cbm](q,x,A)\vdash_{M_G}^{\ast} (q,\lambda,\lambda)[/cbm] влечет [cbm]A\vdash_{G}^{\ast}x[/cbm] (для произвольных [cbm]A\in N[/cbm] и [cbm]x\in V^{\ast}[/cbm] ).

Пусть [cbm]n=1[/cbm] , то есть [cbm](q,x,A)\vdash (q,\lambda,\lambda)[/cbm] . Согласно построению МП-автомата [cbm]M_2[/cbm] , это может быть тогда и только тогда, когда [cbm]x\in A[/cbm] и [cbm]A=x[/cbm] , то есть [cbm]x\vdash^{\ast}x[/cbm] .

Пусть доказываемое верно для любого [cbm]n\leqslant m-1[/cbm] , где [cbm]m\leqslant2[/cbm] , и

[cbm](q,x,A)\vdash^{m} (q,\lambda,\lambda),[/cbm]
(8.14)

причем первый шаг соответствующего вывода имеет вид
[cbm](q,x,A)\vdash (q,x,X_1X_2\ldots X_k).[/cbm]
(8.15)

Это значит, что в системе команд [cbm]\delta[/cbm] есть команда [cbm]q\lambda A\to qX_1X_2X_k[/cbm] и, следовательно, правило в множестве правил вывода [cbm]P[/cbm] грамматики [cbm]G[/cbm] есть правило [cbm]A\to X_1X_2\ldots X_k[/cbm] , по которому указанная команда построена. Из (8.14) и (8.15) следует, что имеет место выводимость

[cbm](q,x, X_1X_2\ldots X_k)\vdash^{\ast}(q,\lambda,\lambda).[/cbm]
(8.16)

Используя индукцию по длине магазинной цепочки [cbm]X_1X_2\ldots X_k[/cbm] , можно доказать, что из (8.16) следует существование таких входных цепочек [cbm]x_1,x_2,\ldots,x_k[/cbm] , что [cbm]x=x_1x_2\ldots x_k[/cbm] и имеет место выводимость

[cbm]\begin{aligned}(q, x_1x_2\ldots x_k, X_1X_2\ldots X_k)&\vdash^{m_1} (q, x_2\ldots x_k, X_2\ldots X_k) \vdash^{m_2}\\ &\vdash^{m_2} (q, x_3\ldots x_k, X_3\ldots X_k) \vdash^{m_3} \ldots\vdash^{m_{k-1}}\\ &\vdash^{m_{k-1}}(q,x_k,X_k)\vdash^{m_{k}} (q,\lambda,\lambda) \end{aligned}[/cbm]
(8.17)

для некоторых [cbm]m_i[/cbm] , таких, что [cbm]1\leqslant m_i<m-1,~i=\overline{1,k}[/cbm] .

Вывод (8.17) можно прокомментировать так: чтобы достичь заключительной конфигурации, [cbm]M_G[/cbm] должен выбросить все символы [cbm]X_1,X_2,\ldots,X_k[/cbm] из магазина. Предположим, что к тому моменту, когда [cbm]X_1[/cbm] покинет магазин (чтобы уже больше туда не вернуться!), будет прочитано некоторое начало входной цепочки [cbm]x[/cbm] — цепочка [cbm]x_1[/cbm] , когда [cbm]X_2[/cbm] покинет магазин, будет прочитана следующая подцепочка [cbm]x_2[/cbm] и так до тех, пока наконец, автомат не прочитает цепочку [cbm]x_k[/cbm] — конец цепочки [cbm]x[/cbm] .

Из теоремы 8.5 следует, что существуют также выводы

[cbm]\begin{aligned}&(q,x_1,X_1)\vdash^{m_1}q;\lambda;\lambda,\\ &(q,x_2,X_2)\vdash^{m_2}(q,\lambda,\lambda),\\ &\cdots\cdots\cdots\cdots\cdots\\ &(q,x_k,X_k)\vdash^{m_k}(q,\lambda,\lambda). \end{aligned}[/cbm]
(8.18)

Все числа [cbm]m_i[/cbm] при [cbm]i=\overline{1,k}[/cbm] не больше [cbm]m-1[/cbm] . Тогда согласно предположению индукции, из (8.18) следует, что для каждого [cbm]i=\overline{1,k}[/cbm] в грамматике [cbm]G[/cbm] имеет место [cbm]X_i\vdash_{G}^{\ast}x_i[/cbm] , и в силу того, что в [cbm]P[/cbm] есть правило вывода [cbm]A\to X_1X_2\ldots X_k[/cbm] , имеем

[cbm]A\vdash X_1X_2\ldots X_k\vdash^{\ast} x_1x_2\ldots x_k=x,[/cbm]

то есть [cbm]A\vdash_{G}^{\ast}x[/cbm] , что и требовалось доказать.

Отсюда, если [cbm]x\in L(M_G)[/cbm] , то [cbm]x\in L(G)[/cbm] , то есть [cbm]L(M_G)\subseteq L(G)[/cbm] , и в силу доказанного выше языки [cbm]L(G)[/cbm] и [cbm]L(M_G)[/cbm] совпадают.

Источник

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

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

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

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