175
правок
Изменения
→Построение МП-автомата по заданной КС-грамматике
Далее будут приведены конструкции для построения МП-автомата по заданной КС-грамматике, и наоборот. Также будут приведены теоремы об эквивалентности языков.
=== Построение МП-автомата по заданной КС-грамматике ===
*1. <tex> \delta(q,\epsilon,A)=\{(q,\beta )| A \rightarrow \beta</tex> — продукция <tex> G \} </tex> — для каждой переменной <tex> A </tex>.
*2. <tex> \delta(q,a,a)=\{(q,\epsilon)\} </tex> для каждого терминала <tex> a </tex>.
Преобразуем грамматику выражений в МП-автомат. Пусть дана грамматика:
*<tex> I \rightarrow a|b|I1|I0|Ia|Ib </tex>
*a) <tex> \delta(q,\epsilon,I)={(q,a), (q,b), (q,Ia), (q,Ib), (q,I0), (q,I1)};</tex>
*b) <tex> \delta(q,\epsilon,E)={(q,I), (q,E+E), (q,E*E), (q,(E))};</tex>
*c) <tex> \delta(q,a,a)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,b,b)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,1,1)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,0,0)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,),))=\{(q,\epsilon)\}</tex>;<tex> \delta(q,(,()=\{(q,\epsilon)\}</tex>;<tex> \delta(q,+,+)=\{(q,\epsilon)\}</tex>;...<tex> \delta(q,*,*)=\{(q,\epsilon)\}</tex>;если входной символ совпадает с вершиной стека, то вершина удаляется.
Пункты a,b образованы по первому правилу построения функции переходов, пункт c по второму правилу.
==== Корректность построения ====
Пусть <tex> w\in L(G)</tex>, тогда <tex> w </tex> имеет следующее левое порождение:
<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 = \epsilon</tex>. Таким образом <tex> (q,w,S)\vdash^*(q,\epsilon,\epsilon) </tex>, т.е допускает <tex> P </tex> по пустому стеку.
{{Теорема
|about= О совпадении КС-языков и множества языков МП-автомата
|statement= Если МП-автомат <tex> P </tex> построен по грамматике <tex> G </tex> по указанной выше конструкции, то <tex> N(P)=\geq L(G) </tex>|proof= Очевидно из того, что мы доказали корректность построения.
}}
