Изменения

#Все символы вида <tex>[pXq]</tex>, где <tex>p</tex> и <tex>q</tex> — состояния из <tex>Q</tex>, а <tex>X</tex> — магазинный символ из <tex>\Gamma</tex>.<br>Грамматика <tex>G</tex> имеет следующие продукции:<br>а) #* продукции <tex>S \rightarrow [q0Z0p]</tex> для всех состояний <tex>p</tex>. Интуитивно символ вида <tex>[q0Z0p]</tex> предназначен для порождения всех тех цепочек <tex>w</tex>, которые приводят <tex>P</tex> к выталкиванию <tex>Z_0</tex> из магазина в процессе перехода из состояния <tex>q_0</tex> в состояние <tex>p</tex>. Таким образом, <tex>(q, w, Z_0) \vdash (q, \epsilon, \epsilon)</tex>. Эти продукции гласят, что стартовый символ <tex>S</tex> порождает все цепочки <tex>w</tex>, приводящие <tex>P</tex> к опустошению магазина после старта в начальной конфигурации;<br>б) #* пусть <tex>\delta(q,a,X)</tex> содержит пару <tex>(r,Y_1Y_2...Y_k)</tex>,где <tex>a</tex> есть либо символ из <tex>\Sigma</tex>, либо <tex>\epsilon</tex>, а <tex>k</tex> — некоторое неотрицательное число; при <tex>k = 0</tex> пара имеет вид <tex>(r, \epsilon)</tex>. Тогда для всех списков состояний <tex>r_1, r_2, ..., r_k</tex> в грамматике <tex>G</tex> есть продукция<br><tex>[qXrkqXr_k] \rightarrow a[rY1r1rY_1r_1][r1Y2r2r_1Y_2r_2]...[rk–1Ykrkr_{k-1}Y_kr_k]</tex>.<br>Она гласит, что один из путей выталкивания <tex>X </tex> и перехода из состояния <tex>q </tex> в состояние rk <tex>r_k</tex> заключается в том, чтобы прочитать <tex>a </tex> (оно может быть равно ε<tex>\epsilon</tex>), затем использовать некоторый вход для выталкивания Y1 <tex>Y_1</tex> из магазина с пере- ходом переходом из состояния <tex>r </tex> в состояние r1<tex>r_1</tex>, далее прочитать некоторый вход, вы- толкнуть Y2 вытолкнуть <tex>Y_2</tex> и перейти из r1 <tex>r_1</tex> в r2<tex>r_2</tex>, и т.д.

 Докажем корректность неформальной интерпретации переменных вида <tex>[qXp]</tex>: