Изменения

|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G) - \setminus \mathcal {f}\varepsilon\mathcal {g}</tex>.

<tex>A \overset{*}{\underset{G'}{\Rightarrow}}^*w</tex> тогда и только тогда, когда <tex>A \overset{*}{\underset{G}{\Rightarrow}}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).

Пусть <tex>A \overset{*}{\underset{G'}{\Rightarrow}}^*w</tex>. Несомненно, <tex>w \ne \varepsilon</tex>, поскольку <tex>G'</tex> - грамматика без <tex>\varepsilon</tex>-правил.<br/>Докажем индукцией по длине порождения, что <tex>A \overset{*}{\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 \overset{*}{\underset{G}{\Rightarrow}}^*w</tex>, где на шагах после первого, из всех нетерминалов в цепочке <tex>\alpha</tex> выводиться <tex>\varepsilon</tex>.<br/>:'''Предположение'''. Пусть из <tex>A \overset{*}{\underset{G'}{\Rightarrow}}^*w</tex> следует, что <tex>A \overset{*}{\underset{G}{\Rightarrow}}^*w</tex> и <tex>w \ne \varepsilon</tex> верно для <tex>p < n</tex>.<br/>

\overset{*}{\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 \overset{*}{\underset{G'}{\Rightarrow}}^*w_i</tex>. Если <tex>X_i</tex> есть терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \overset{*}{\underset{G'}{\Rightarrow}}^*w_i</tex> содержит менее <tex>n</tex> шагов.<br/> По предположению <tex>X_i \overset{*}{\underset{G}{\Rightarrow}}^*w_i</tex>.<br/>

:<tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} ^* X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}} ^* w_1 w_2...w_k = w</tex><br/>

Пусть <tex>A \overset{*}{\underset{G}{\Rightarrow}}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/> Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G'}{\Rightarrow}}^*w</tex>.<br/>

<tex>A \rightarrow w</tex> является правилом в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \overset{*}{\underset{G'}{\Rightarrow}}^*w</tex>.:'''Предположение'''. Пусть из <tex>A \overset{*}{\underset{G}{\Rightarrow}}^*w</tex> и <tex>w \ne \varepsilon следует, что A \overset{*}{\underset{G'}{\Rightarrow}}^*w </tex> верно для <tex>p < n</tex>.<br/>

\overset{*}{\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 \overset{*}{\underset{G'}{\Rightarrow}}^*w_i</tex>.<br/>

Утверждаем, что <tex> X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}}^*w</tex>, поскольку только <tex>Y_j</tex>, которых нет среди <tex>X_1, X_2, ... X_k</tex>, использованы для порождения <tex>\varepsilon</tex> и не вносят ничего в порождение <tex>w</tex>.Так как каждое из порождений <tex>Y_j \overset{*}{\underset{G}{\Rightarrow}}^*w_j</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что если <tex>w_j \ne \varepsilon</tex>, то <tex>Y_j \overset{*}{\underset{G'}{\Rightarrow}}^*w_j</tex>.<br/>Таким образом <tex>A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \overset{*}{\underset{G'}{\Rightarrow}} ^* w</tex>.<br/>