175
правок
Изменения
→Пример
Также грамматика имеет следующие продукции:
*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,\epsilon)\} </tex> получаем продукцию <tex> [qZq] \rightarrow \epsilon </tex>
==== Корректность построения ====
Докажем, что если <tex> (q,w,X) \vdash^* (p,\epsilon,\epsilon)</tex>, то <tex> [q,X,p] \Rightarrow^* w </tex>.
