Изменения

'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S ' \rangle</tex> без <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил). <tex>L(G') = L(G)</tex>.

# Если в исходной грамматике <tex>G</tex> выводилось пустое слово <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правила <tex>S' \rightarrow S|\varepsilon</tex>.

В этом случае в <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>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>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^* X_1 X_2...X_k \underset{G}{\Rightarrow}^* w_1 w_2...w_k = w</tex><br/>.Ч.т.д.<br/>

'''Предположение'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G'}{\Rightarrow}^*w </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_1Y_{i_1}, X_2Y_{i_2}, ... X_k, Y_{i_p}</tex> будут теми — подпоследовательность, состоящая из всех элементов, таких, что <tex>Y_jw_{i_k} \ne \varepsilon</tex> (в порядке записи), для которых то есть <tex>w_i Y_{i_1} Y_{i_2} ... Y_{i_p} \ne underset{G}{\varepsilonRightarrow}^*w</tex>. <tex>k p \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>.<br/> Таким образом , <tex>A \rightarrow X_1 X_2 Y_{i_1}, Y_{i_2}, ... X_k, Y_{i_p}</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<br/tex>.Так как каждое из порождений <tex>Y_j Y_i \underset{G}{\Rightarrow}^*w_jw_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что , если <tex>w_j w_i \ne \varepsilon</tex>, то <tex>Y_j Y_i \underset{G'}{\Rightarrow}^*w_jw_i</tex>.<br/>Таким образом , <tex>A \underset{G'}{\rightarrowRightarrow} X_1 X_2 ... X_k \underset{G'}{\Rightarrow}^* w</tex>.<br/>Ч.т.д.