175
правок
Изменения
→Корректность построения
*База. Пара <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>. По построению <tex> G </tex> существует продукция <tex> [qXr_k] \rightarrow a[r_0 Y_1 r_1][r_1 Y_2 r_2]...[r_{k-1} Y_k r_k] </tex>, где <tex> r_i</tex> — состояния из <tex> Q </tex>, и <tex> r_k = p </tex>. Пусть <tex> X=w_1 w_2 ... w_k </tex>, где <tex> w_i </tex> — входная цепочка, которая прочитывается до удаления <tex> Y_i </tex> из стека, тогда <tex> (r_{i-1},w_i, Y_i) \vdash^* (r_i, \epsilon, \epsilon)</tex>.
