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>.
