175
правок
Изменения
→Корректность построения
==== Корректность построения ====
Докажем, что если <tex> (q,w,X) \vdash^* (p,\epsilon,\epsilon)</tex>, то <tex> [q,X,pqXp] \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>. Первый переход должен иметь вид:
