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

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

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

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

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


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

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


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


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


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


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


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


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

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

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


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

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


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


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


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

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


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

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

[math](q,aacbc,S)\vdash (q,aacbc,aS)\vdash (q,acbc,S)\vdash (q,acbc,c).[/math]



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


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


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


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

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


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

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


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


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


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


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

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


[math](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).[/math]

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


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

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


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


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


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


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


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

причем первый шаг соответствующего вывода имеет вид

[math](q,x,A)\vdash (q,x,X_1X_2\ldots X_k).[/math]
(8.15)

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


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

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


[math]\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}[/math]
(8.17)

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


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


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


[math]\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}[/math]
(8.18)

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


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

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


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


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


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

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