Изменения
→Доказательство корректности
<tex>\Rightarrow)</tex><br\>
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порожденияв грамматике <tex>G'</tex>, что <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/>
'''База'''. <tex>A \underset{G'}{\Rightarrow} w</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>.<br/>'''Предположение'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex> менее, чем за <tex>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/>
<tex>\Leftarrow)</tex><br/>
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порожденияв грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>
'''База'''. <tex>A \underset{G}{\Rightarrow} w</tex>.<br/>
Правило <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>
'''Предположение'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex> менее, чем за <tex>n</tex> шагов.<br/>'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m\underset{G}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>.<br/>
Пусть <tex>X_1, X_2, ... X_k</tex> будут теми из <tex>Y_j</tex> (в порядке записи), для которых <tex>w_i \ne \varepsilon</tex>. <tex>k \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>.<br/> Таким образом <tex>A \rightarrow X_1 X_2 ... X_k</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>.
Утверждаем, что <tex> X_1 X_2...X_k \underset{G}{\Rightarrow}^*w</tex>, поскольку только <tex>Y_j</tex>, которых нет среди <tex>X_1, X_2, ... X_k</tex>, использованы для порождения <tex>\varepsilon</tex> и не вносят ничего в порождение <tex>w</tex>.
