175
правок
Изменения
→Построение КС-грамматики по МП-автомату
*a) продукции <tex> S \rightarrow [q_0,Z_0,p] </tex> для всех <tex> p </tex>, таким образом <tex> (q,w,Z_0)\vdash^* (q,\epsilon,\epsilon)</tex>
*b) пусть <tex> \delta(q,a,X) </tex> содержит <tex> (r,Y_1,Y_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,\epsilon)\}</tex>
Так как <tex> P </tex> имеет один магазинный символ и одно состояние, то грамматика строится просто. У нас будет всего две переменные:
*a) <tex> S </tex> — стартовый символ.
*b) <tex> [qZq] </tex> — единственная тройка, которую можно собрать из наших состояний и магазинный символов.
Также грамматика имеет следующие продукции:
*1. Единственной продукцией для <tex> S </tex> является <tex> S \rightarrow [qZq] </tex>. Но если бы у автомата было <tex> n </tex> состояний, то тут бы имелось и <tex> n </tex> продукций.
*2.
==== Корректность построения ====
Докажем, что если <tex> (q,w,X) \vdash^* (p,\epsilon,\epsilon)</tex>, то <tex> [q,X,p] \Rightarrow^* w </tex>.
