Изменения

# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

Достаточность данных действий следует из доказанной выше теоремы.

Докажем, что после выполнения второго шага не могут появиться новые непорождающие нетерминалы.

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> конечной цепочки терминалов, то было удалено хотя бы какое-то одно правило из этого вывода. Возьмем первое удалённое правило <tex>B\rightarrow\alpha</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

<tex>

\begin{array}{l l}