175
правок
Изменения
→Корректность построения
Докажем, что если <tex> (q,w,X) \vdash^* (p,\epsilon,\epsilon)</tex>, то <tex> [q,X,p] \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,Z) \vdash (r_0,X,Y_1Y_2...Y_k) \vdash^* (p,\epsilon,\epsilon) </tex>, где <tex> w=aX </tex> для некоторого <tex> a </tex>, которое является либо символом из <tex> \Gamma </tex>, либо <tex> \epsilon </tex>.
