Изменения

*<tex> S \rightarrow 0S1 </tex>;*<tex> S \rightarrow 1S0 </tex>;*<tex> S \rightarrow \varepsilon </tex>.

a) * <tex>\delta(q, \varepsilon, S) = \{(q, 0S1), (q, 1S0), (q, \varepsilon)\}</tex> (в соответствии с первым пунктом построения <tex>\delta</tex>);

b) * <tex> \delta(q, 0, 0)= \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 1, 1)= \{(q, \varepsilon)\}</tex> (в соответствии со вторым пунктом построения <tex>\delta</tex>).

Пусть у нас имеется МП-автомат <tex> PA =(\{q\},langle \{i,e\},\{Z\},\delta{q\},q,Z), \delta \rangle</tex>, функция <tex> \delta </tex> задана следующим образом:*<tex> \delta(q,i,Z)=\{(q,ZZ)\}</tex>,*<tex> \delta(q,e,Z)=\{(q,\varepsilon)\}</tex>.Так как <tex> P </tex> имеет один магазинный символ и одно состояние, то грамматика строится просто. У нас будет всего две переменные:

a) <tex> S </tex> — стартовый символ[[Файл:Example2.png]]

b) Так как стековый алфавит <tex> [qZq] A</tex> — единственная тройкасодержит лишь один символ и одно состояние, которую можно собрать из наших состояний и магазинных символов.то в построенной грамматике будет лишь 2 нетерминала:

* <tex>S</tex> — стартовый нетерминал. * <tex>[qZq]</tex> — единственная тройка, которую можно собрать из состояний автомата и символов стекового алфавита. Также грамматика имеет следующие продукцииправила вывода:* Единственной продукцией для <tex> S </tex> является <tex> S \rightarrow [qZq] </tex>. Но если бы у автомата было <tex> n </tex> состояний, то тут бы имелось и <tex> n </tex> продукций.* Из того факта, что <tex> \delta(q,i,Z) </tex> содержит <tex> (q,ZZ)</tex>, получаем продукцию правило вывода <tex> [qZq] \rightarrow i[qZq][qZq] </tex>. Если бы у автомата было '''<tex>n''' </tex> состояний, то такое правило порождало такой переход порождал бы <tex> n^2 </tex> продукций.* Из <tex> \delta(q,e,Z)=\{(q,\varepsilon)\} </tex> получаем продукцию правило вывода <tex> [qZq] \rightarrow \varepsilon e</tex>Для удобства тройку <tex> [qZq] </tex> можно заменить символом <tex> A </tex>, в таком случае грамматика состоит из следующих продукцийправила вывода в грамматике будут следующие:* <tex> S \rightarrow A</tex>;* <tex> A \rightarrow iAA | </tex>;* <tex>A \varepsilonrightarrow e</tex>.В действительности можно заметитьУпростим грамматику, что заменив <tex>SA</tex> и на <tex>AS</tex> порождают одни и те же цепочки(очевидно, поэтому их можно обозначить одинаковоона не поменяется), итого: и получим в результате <tex> G\Gamma =(\langle\{Si,e\},\{i,eS\}, S,\{S \rightarrow iSS| e\varepsilon}\},S)rangle</tex>