Изменения

*<tex>[qXp] ⇒ \Rightarrow w </tex> тогда и только тогда, когда <tex>(q, w, X) |− \vdash (p, ε\epsilon, ε\epsilon)</tex>.

''(Достаточность) '' Пусть <tex>(q, w, X) |− \vdash (p, ε\epsilon, ε\epsilon)</tex>. Докажем, что <tex>[qXp] ⇒ \Rightarrow w</tex>, используя ин-дукцию индукцию по числу переходов МП-автомата.

'''Базис. ''' Один шаг. Пара <tex>(p, ε\epsilon) </tex> должна быть в δ<tex>\delta(q, w, X)</tex>, и <tex>w </tex> есть либо одиночный символ, либо ε<tex>\epsilon</tex>. Из построения <tex>G </tex> следует, что <tex>[qXp] → \rightarrow w </tex> является продукцией, поэто- му поэтому <tex>[qXp] ⇒ \Rightarrow w</tex>.*'''Индукция. ''' Предположим, что последовательность <tex>(q, w, X) |− \vdash (p, ε\epsilon, ε\epsilon) </tex> состоит из <tex>n</tex> переходов, и <tex>n > 1</tex>. Первый переход должен иметь вид * <tex>(q, w, X) |− \vdash (r0r_0, X, Y1Y2Y_1Y_2...YkY_k) |− \vdash (p, ε\epsilon, ε\epsilon)</tex>, где <tex>w = aX </tex> для некоторого <tex>a</tex>, которое является либо символом из Σ<tex>\Sigma</tex>, либо ε<tex>\epsilon</tex>. Отсюда следу- ет, что пара (r0, Y1Y2...Yk) должна быть в δ(q, a, X). Кроме того, по построению G сущест- вует продукция [qXrk] → a[r0Y1r1][r1Y2r2]...[rk–1Ykrk], у которой rk = p и r1, r2, ..., rk–1 — не- которые состояния из Q.