Изменения
Нет описания правки
Далее будут приведены конструкции для построения МП-автомата по заданной КС-грамматике, и наоборот. Также будет приведена теорема об эквивалентности языков, задаваемых ими.
=== Построение МП-автомата по заданной КС-грамматике ===
Пусть <tex> G=(V,T,Q,S) </tex> — КС-грамматика. Построим МП-автомат <tex> P=(\{q\},T,V \cup T, \delta ,q,S) </tex>, который допускает <tex> L(G) </tex> по пустому магазину. Функция переходов <tex> \delta </tex> будет определена по следующим правилам:
*1. <tex> \delta(q,\epsilonvarepsilon,A)=\{(q,\beta )| A \rightarrow \beta</tex> — продукция <tex> G \} </tex> — для каждой переменной <tex> A </tex>. *2. <tex> \delta(q,a,a)=\{(q,\epsilonvarepsilon)\} </tex> для каждого терминала <tex> a </tex>.
==== Пример ====
Преобразуем грамматику выражений в МП-автомат. Пусть дана грамматика:
*<tex> I \rightarrow a|b|I1|I0|Ia|Ib </tex>,*<tex> E \rightarrow I|E*E|E+E|(E) </tex>.Множеством входных символов является <tex> \{a,b,1,0,(,),+,*\} </tex>. Эти символы, вместе с переменными <tex> I,E </tex>, образуют магазинный алфавит. Функция переходов определена следующим образом:*a) <tex> \delta(q,\epsilonvarepsilon,I)={(q,a), (q,b), (q,Ia), (q,Ib), (q,I0), (q,I1)};</tex>*b) <tex> \delta(q,\epsilonvarepsilon,E)={(q,I), (q,E+E), (q,E*E), (q,(E))};</tex>*c) <tex> \delta(q,a,a)=\{(q,\epsilonvarepsilon)\}</tex>; <tex> \delta(q,b,b)=\{(q,\epsilonvarepsilon)\}</tex>;...<tex> \delta(q,*,*)=\{(q,\epsilonvarepsilon)\}</tex>; если . Если входной символ совпадает с вершиной стека, то вершина удаляется.Пункты '''a,b''' образованы по первому правилу построения функции переходов, а пункт '''c''' по второму правилу.
==== Корректность построения ====
<tex> S = \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n=w</tex>.
Покажем индукцией по <tex> i </tex>, что <tex> (q,w,S)\vdash^*(q,y_i,\alpha_i)</tex>:
*База. Очевидно, что <tex> (q,w,S)\vdash^*(q,w,S) </tex>.
*Переход. Предположим, что <tex> (q,w,S)\vdash^*(q,w_i,\alpha_i) </tex>. Заметим, что шаг порождения <tex> y_i \Rightarrow y_{i+1}</tex> включает замену некоторой переменной <tex> A </tex> ее продукцией <tex> \beta </tex>. Правило 1 построения МП-автомата позволяет на заменить <tex> A </tex> на вершине стека на цепочку <tex> \beta </tex>, а правило 2 позволяет затем сравнить любые терминалы на вершине со входными символами. В результате достигается МО <tex> (q,y_{i+1},\alpha_{i+1}) </tex>.
*Также заметим, что <tex> \alpha_n = \epsilonvarepsilon</tex>. Таким образом <tex> (q,w,S)\vdash^*(q,\epsilonvarepsilon,\epsilonvarepsilon) </tex>, т.е допускает <tex> P </tex> по пустому стеку.
{{Утверждение
|about=1
Следует отметить, что удаление <tex> X </tex> может являться результатом множества переходов.<br>
Пусть <tex> P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0)</tex> — МП-автомат. Построим <tex> G=(V,\Sigma,R,S)</tex>, где <tex> V </tex> состоит из:
*1 Специальный стартовый символ <tex> S </tex>,
*2 Все символы вида <tex> [pXq]</tex>, где <tex> p </tex> и <tex> q </tex> — состояния из <tex> Q </tex>, а <tex> X </tex> — магазинный символ из <tex> \Gamma </tex>.
Грамматика <tex> G </tex> имеет следующие продукции:
*a) продукции <tex> S \rightarrow [q_0Z_0p] </tex> для всех <tex> p </tex>, таким образом <tex> (q,w,Z_0)\vdash^* (q,\epsilonvarepsilon,\epsilonvarepsilon)</tex>
*b) пусть <tex> \delta(q,a,X) </tex> содержит <tex> (r,Y_1Y_2...Y_k)</tex>. Тогда для всех списков состояний <tex> r_1,r_2,...,r_k</tex> в грамматике <tex> G </tex> есть продукция <tex> [qXr_k]\rightarrow a[r Y_1 r_1][r_1 Y_1 r_2]...[r_{k-1} Y_k r_k]</tex>.
==== Пример ====
Пусть у нас имеется <tex> P=(\{q\},\{i,e\},\{Z\},\delta,q,Z)</tex>, функция <tex> \delta </tex> задана следующим образом:
*<tex> \delta(q,i,Z)=\{(q,ZZ)\}</tex>,*<tex> \delta(q,e,Z)=\{(q,\epsilonvarepsilon)\}</tex>.
Так как <tex> P </tex> имеет один магазинный символ и одно состояние, то грамматика строится просто. У нас будет всего две переменные:
*a) <tex> S </tex> — стартовый символ.
*1. Единственной продукцией для <tex> S </tex> является <tex> S \rightarrow [qZq] </tex>. Но если бы у автомата было <tex> n </tex> состояний, то тут бы имелось и <tex> n </tex> продукций.
*2. Из того факта, что <tex> \delta(q,i,Z) </tex> содержит <tex> (q,ZZ)</tex>, получаем продукцию <tex> [qZq] \rightarrow i[qZq][qZq] </tex>. Если бы у автомата было '''n''' состояний, то такое правило порождало бы <tex> n^2 </tex> продукций.
*3. Из <tex> \delta(q,e,Z)=\{(q,\epsilonvarepsilon)\} </tex> получаем продукцию <tex> [qZq] \rightarrow \epsilon varepsilon </tex>
Для удобства тройку <tex> [qZq] </tex> можно заменить символом <tex> A </tex>, в таком случае грамматика состоит из следующих продукций:
* <tex> S \rightarrow A</tex>
* <tex> A \rightarrow iAA | \epsilonvarepsilon</tex>В действительности можно заметить, что <tex>S</tex> и <tex>A</tex> порождают одни и те же цепочки, поэтому их можно обозначить одинаково, итого: <tex> G=(\{S\},\{i,e\},\{S \rightarrow iSS| \epsilonvarepsilon\},S)</tex>
==== Корректность построения ====
Докажем, что если <tex> (q,w,X) \vdash^* (p,\epsilonvarepsilon,\epsilonvarepsilon)</tex>, то <tex> [qXp] \Rightarrow^* w </tex>.*База. Пара <tex> (p,\epsilonvarepsilon) </tex> должна быть в <tex> \delta(q,w,X) </tex> и <tex> w </tex> есть одиночный символ, или <tex> \epsilon varepsilon</tex>. Из построения <tex> G </tex> следует, что <tex> [qXp] \rightarrow w </tex> является продукцией, поэтому <tex> [qXp] \Rightarrow w </tex>.*Переход. Предположим, что последовательность <tex> (q,w,X) \vdash^* (p,\epsilonvarepsilon,\epsilonvarepsilon)</tex> состоит из <tex> n </tex> переходов, и <tex> n>1 </tex>. Первый переход должен иметь вид:<tex> (q,w,Z) \vdash (r_0,X,Y_1Y_2...Y_k) \vdash^* (p,\epsilonvarepsilon,\epsilonvarepsilon) </tex>, где <tex> w=aX </tex> для некоторого <tex> a </tex>, которое является либо символом из <tex> \Gamma </tex>, либо <tex> \epsilon varepsilon </tex>. По построению <tex> G </tex> существует продукция <tex> [qXr_k] \rightarrow a[r_0 Y_1 r_1][r_1 Y_2 r_2]...[r_{k-1} Y_k r_k] </tex>, где <tex> r_i</tex> — состояния из <tex> Q </tex>, и <tex> r_k = p </tex>. Пусть <tex> X=w_1 w_2 ... w_k </tex>, где <tex> w_i </tex> — входная цепочка, которая прочитывается до удаления <tex> Y_i </tex> из стека, тогда <tex> (r_{i-1},w_i, Y_i) \vdash^* (r_i, \epsilonvarepsilon, \epsilonvarepsilon)</tex>. По скольку ни одна из этих последовательностей переходов не содержит более, чем <tex> n </tex> переходов, к ним можно применить предположение индукции <tex> [r_{i-1}Y_ir_i] \Rightarrow^* w_i</tex>. Соберем эти порождения вместе: <br>
<tex> [qXr_k] \Rightarrow a[r_0Y_1r_1][r_1Y_1r_2]...[r_{k-1}Y_kr_k] \Rightarrow^* aw_1[r_1Y_1r_2]...[r_{k-1}Y_kr_k] \Rightarrow^* aw_1w_2[r_2Y_3r_3]...[r_{k-1}Y_kr_k] \Rightarrow^*... \Rightarrow^* aw_1w_2...w_k = w</tex>.
{{Утверждение
|about=2
|statement= Если КС-грамматика <tex> G </tex> построена по МП-автомату <tex> P </tex>, с использованием указанной выше конструкции, то <tex> N(P) \subseteq L(G) </tex>.
|proof= Выше доказана корректность построения КС-грамматики по МП-автомату. Значит языки допускаемые МП-автоматами являются подмножеством языков, заданных КС-грамматикой.
}}
