170
правок
Изменения
Нет описания правки
*<tex> \delta(q,e,Z)=\{(q,\varepsilon)\}</tex>.
Так как <tex> P </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,\varepsilon)\} </tex> получаем продукцию <tex> [qZq] \rightarrow \varepsilon </tex>
Для удобства тройку <tex> [qZq] </tex> можно заменить символом <tex> A </tex>, в таком случае грамматика состоит из следующих продукций:
* <tex> S \rightarrow A</tex>
