175
правок
Изменения
→Пример
*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> [qZq] </tex> можно заменить символом <tex> A </tex>, в таком случае грамматика состоит из следующих продукций:
* <tex> S \rightarrow A</tex>
* <tex> A \rightarrow iAA | \epsilon</tex>
В действительности можно заметить, что <tex>S</tex> и <tex>A</tex> порождают одни и те же цепочки, поэтому их можно обозначить одинаково, итого: <tex> G=(\{S\},\{i,e\},\{S \rightarrow iSS| \epsilon\},S)</tex>
==== Корректность построения ====
