Изменения

Сначала по <tex>G </tex> построим грамматику <tex>G'' = (N'', T, P'', S)</tex>, как в доказательстве леммы 1. По <tex>G'' </tex> построим грамматику <tex>G'</tex>, в которой:* <tex>N' = N'' U \cup \{D\}</tex>, где <tex>D </tex> {{---}} новый символ,* <tex>P' </tex> получаем из <tex>P'' </tex> заменой всех правил вида <tex>\alpha \rightarrow \beta \in P''</tex>, где <tex>|\alpha| > |\beta| </tex> на правила вида <tex>\alpha \rightarrow \betaDbeta D^{|\alpha| - |\beta|}</tex>, и добавлением правила <tex>D \rightarrow \varepsilon</tex>. Теперь все правила в <tex>P' </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> нет.

Покажем, что L(G') = L(G).Заметим, что замена правила \alpha \rightarrow \beta на \alpha \rightarrow \betaD^{|\alpha| - |\beta|} не меняет язык грамматики, потому что дополнительная буква D запрещается при добавлении перехода D \rightarrow \varepsilon, а других правил для D нет.Тогда получаем, что <tex>L(G) <= L(G')</tex>, аналогично обратные изменения не меняют язык, то есть <tex>L(G') <= L(G)</tex>.