Изменения
→Доказательство корректности алгоритма
Обозначим длину порождения за <tex>p</tex>.
:'''Базис'''. <tex>p = 1</tex><br/>
В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. Согласно конструкции <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha-</tex> это <tex>w</tex>, символы которой, возможно, перемежаются <tex>\varepsilon-</tex> -порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}^*w</tex>, где на шагах после первого, из всех нетерминалов в цепочке <tex>\alpha</tex> выводиться <tex>\varepsilon</tex>.<br/>
:'''Предположение'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w</tex> следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> верно для <tex>p < n</tex>.<br/>
:'''Переход'''. <tex>p = n</tex><br/>
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k
\underset{G'}{\Rightarrow}w^*</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где цепочка <tex>Y_1 Y_2...Y_m</tex> совпадает с цепочкой <tex>X_1 X_2...X_k</tex>, цепочка <tex>Y_1 Y_2...Y_m</tex>, возможно, перемежаются <tex>\varepsilon-</tex> -порождающими нетерминалами.<br/>
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> есть терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов.<br/> По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>.<br/>
Теперь построим соответствующее порождение в <tex>G</tex>.<br/>
