Изменения

Заменяем разрешенные в <tex>w'</tex> символы на новые и получаем, что <tex>w \in L(G')</tex>.

Пусть <tex>x \in L(G')</tex>. Тогда в <tex>G'</tex> существует вывод <tex>S \Rightarrow^* x</tex>. Мы можем поменять порядок применения правил в этом выводе: сначала применяем только правила вида <tex>\alpha' \rightarrow \beta'</tex>, а потом только правила вида <tex>a' \rightarrow a</tex>.

Получаем вывод в <tex>G</tex>: <tex>S = x_0 \Rightarrow x_1 \Rightarrow ... \Rightarrow x_n = x</tex>.

Таким образом, <tex>L(G') = L(G)</tex>.

Заметим, что замена правила <tex>\alpha \rightarrow \beta</tex> на <tex>\alpha \rightarrow \beta D^{|\alpha| - |\beta|}</tex> не меняет язык грамматики, потому что дополнительная буква <tex>D</tex> запрещается при добавлении перехода <tex>D \rightarrow \varepsilon</tex>, а других правил для <tex>D</tex> нет.

}}

Покажем, что <tex>L(G') = L(G)</tex>.

* все правила из <tex>P_1</tex> применимы к обеим грамматикам,

* шаг вывода <tex>\gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1CDE\beta'\gamma_2</tex>, благодаря правилу <tex>p = AB\alpha \rightarrow CDE\beta' \in P_2</tex> в <tex>G</tex>может быть использавано в <tex>G'</tex> с помощью трех шагов:

Таким образом, для <tex>r \in P_2 \cup P_3</tex> мы можем заменить все применения <tex>P_r</tex> на <tex>r</tex>, то есть получаем вывод <tex>w</tex>, который состоит только из правил из <tex>P</tex>.

}}