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

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

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

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


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

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


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


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


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


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


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


q\lambda S\to qaSbS\mid qaS\mid qc,\qquad qaa\to q\lambda,\qquad qbb\to q\lambda,\qquad qcc\to q\lambda

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


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


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

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


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


Прочитаем цепочку aacbc:


\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}

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


S\vdash aSbS\vdash aaSbS\vdash aacbS\vdash aacbc,

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


(q,aacbc,S)\vdash (q,aacbc,aS)\vdash (q,acbc,S)\vdash (q,acbc,c).



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


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


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


(q,x,A)\vdash_{M_G}^{\ast}(q,\lambda,\lambda).

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


\bigl(q,x(1)\ldots x(k),A\bigr)\vdash \bigl(q,x(1)\ldots x(k),x(1)\ldots x(k)\bigr).

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


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


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


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


(q,x_i,X_i)\vdash^{\ast}(q,\lambda,\lambda),

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


(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).

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


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

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


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


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


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


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


(q,x,A)\vdash^{m} (q,\lambda,\lambda),
(8.14)

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


(q,x,A)\vdash (q,x,X_1X_2\ldots X_k).
(8.15)

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


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

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


\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}
(8.17)

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


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


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


\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}
(8.18)

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


A\vdash X_1X_2\ldots X_k\vdash^{\ast} x_1x_2\ldots x_k=x,

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


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

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

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


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

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