# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
При удалении из грамматики непорождающих нетерминалов и правил, их содержащих, язык не изменится, так как эти нетерминалы по определению не могли встречаться в выводе любого слова.
{{Определение
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
При удалении из грамматики недостижимых нетерминалов и правил, их содержащих, язык не изменится, так как эти нетерминалы недостижимы из стартового, то и в выводе любого слова они встречаться не могли.
{{Определение
}}
==Алгоритм==
Алгоритм удаления бесполезных нетерминалов из грамматики прост, как три рубля.
# Удалить из грамматики непорождающие нетерминалы и правила, в которых они встречаются.
# Удалить из грамматики недостижимые нетерминалы и правила, в которых они встречаются.
После сих действий в грамматике не будет бесполезных символов.
==Корректность алгоритма==
Корректность алгоритма вытекает из [[#th1|первой теоремы]] и следующей.
{{Теорема
|id=th2
|statement=
Пусть <tex>\Gamma</tex> {{---}} КС-грамматика, и <tex>L(\Gamma)\ne\varnothing</tex>без непорождающих нетерминалов. Пусть <tex>\Gamma_1</tex> - грамматика, полученная с помощью следующих двух шагов: 1) Удаляются Тогда после удаления недостижимых нетерминалов новые непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>\Gamma_2</tex> {{---}} полученная в результате грамматика. 2) Удаляются все символы, недостижимые из <tex>\Gamma_2</tex>. Тогда <tex>\Gamma_1</tex> не имеет бесполезных символов и <tex>L(\Gamma_1)=L(\Gamma)</tex>появятся.
|proof=
Пусть Допустим, что в грамматике появился непорождающий нетерминал <tex>XA</tex> {{---}} оставшийся символ. Известно, что Так как до удаления недостижимых нетерминалов существовал вывод из <tex>X\overset{*}{\underset{\Gamma}{\Rightarrow}} wA</tex> для некоторой конечной цепочки <tex>w</tex> из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\overset{*}{\underset{\Gamma_2}{\Rightarrow}}w</tex>то удалилось какое-то одно или несколько правил из вывода. Поскольку <tex>X</tex> не был удален на втором шаге, известно, что существует такие Возьмем первое удаленное правило <tex>C\alpha</tex> и <tex>\beta</tex>, для которых <tex>S\overset{*}{\underset{\Gamma_2}{\Rightarrow}} rightarrow\alpha X\beta</tex>. Кроме того, каждый символОно могло удалиться только, использованный если в этом порождении, достижим, поэтому <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta</tex>присутствуют недостижимые символы. Также известноНо так как было выбрано первое удаленное правило из вывода, что каждый символ в цепочке то <tex>\alpha X\betaC</tex> — достижим, поэтому каждый из них является порождающим в <tex>\Gamma_2</tex>. Порождение некоторой терминальной цепочки, напримера, <tex>\alpha X\beta\overset{*}{\underset{\Gamma_2}{\Rightarrow}} xwy</tex>следовательно, содержит только и все символы, достижимые из <tex>S</tex>, поскольку они достижимы из символов в цепочке <tex>\alpha X\beta</tex>. Таким образомЗначит, это порождение есть также порождение в <tex>\Gamma_1</tex>, то есть <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta\overset{*}{\underset{\Gamma_1}{\Rightarrow}} xwy</tex>. Итак, <tex>X</tex> полезен в <tex>\Gamma_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>\Gamma_1</tex> можно заключить, что <tex>\Gamma_1</tex> правило удалиться не имеет бесполезных символов. <tex>L(\Gamma_1)\subseteq L(\Gamma)</tex>, так как при построении <tex>\Gamma_1</tex> из <tex>\Gamma</tex> символы и продукции только убирались. Докажем, что <tex>L(\Gamma_1)\supseteq L(\Gamma)</tex>. Если <tex>w\in L(\Gamma)</tex>, то <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в <tex>\Gamma_1</tex> его также содержит. Таким образом, <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} w</tex>, <tex>w\in L(\Gamma_1)</tex> и <tex>L(\Gamma)=L(\Gamma_1)</tex>могло.
}}
