Изменения

Пусть <tex>G\Gamma</tex> {{---}} КС-грамматика, и <tex>L(G\Gamma)\ne\varnothing</tex>. Пусть <tex>G_1\Gamma_1</tex> - грамматика, полученная с помощью следующих двух шагов:

1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>G_2\Gamma_2</tex> {{---}} полученная в результате грамматика.

2) Удаляются все символы, недостижимые из <tex>G_2\Gamma_2</tex>.

Тогда <tex>G_1\Gamma_1</tex> не имеет бесполезных символов и <tex>L(G_1\Gamma_1)=L(G\Gamma)</tex>.

Пусть <tex>X</tex> {{---}} оставшийся символ. Известно, что <tex>X\overset{*}{\underset{\Gamma}{\Rightarrow _G^* }} w</tex> для некоторой цепочки <tex>w</tex> из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\overset{*}{\underset{\Gamma_2}{\Rightarrow _{G_2}^* }w</tex>.

Поскольку <tex>X</tex> не был удален на втором шаге, известно, что существует такие <tex>\alpha</tex> и <tex>\beta</tex>, для которых <tex>S\overset{*}{\underset{\Gamma_2}{\Rightarrow _{G_2}^* } \alpha X\beta</tex>. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow _{G_1}^* } \alpha X\beta</tex>.

Также известно, что каждый символ в цепочке <tex>\alpha X\beta</tex> достижим, поэтому каждый из них является порождающим в <tex>G_2\Gamma_2</tex>. Порождение некоторой терминальной цепочки, например, <tex>\alpha X\beta\overset{*}{\underset{\Gamma_2}{\Rightarrow _{G_2}^* } xwy</tex>, содержит только символы, достижимые из <tex>S</tex>, поскольку они достижимы из символов в цепочке <tex>\alpha X\beta</tex>. Таким образом, это порождение есть также порождение в <tex>G_1\Gamma_1</tex>, то есть <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow _{G_1}^* } \alpha X\beta\overset{*}{\underset{\Gamma_1}{\Rightarrow _{G_1}^* } xwy</tex>.

Итак, <tex>X</tex> полезен в <tex>G_1\Gamma_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>G_1\Gamma_1</tex> можно заключить, что <tex>G_1\Gamma_1</tex> не имеет бесполезных символов.

<tex>L(G_1\Gamma_1)\subseteq L(G\Gamma)</tex>, так как при построении <tex>G_1\Gamma_1</tex> из <tex>G\Gamma</tex> символы и продукции только убирались. Докажем, что <tex>L(G_1\Gamma_1)\supseteq L(G\Gamma)</tex>. Если <tex>w\in L(G\Gamma)</tex>, то <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow _{G}^* } w</tex>. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в <tex>G_1\Gamma_1</tex> его также содержит. Таким образом, <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow _{G_1}^* } w</tex>, <tex>w\in L(G_1\Gamma_1)</tex> и <tex>L(G\Gamma)=L(G_1\Gamma_1)</tex>.