Изменения

Символ Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.

После сих действий в грамматике не будет == Алгоритм удаления бесполезных символовнетерминалов ==# Удалить из грамматики правила, содержащие непорождающие нетерминалы.# Удалить из грамматики правила, содержащие недостижимые нетерминалы. 

Пусть <tex>\Gamma</tex> - грамматика без непорождающих нетерминалов. Тогда после удаления недостижимых нетерминалов новые непорождающие не появятсяАлгоритм корректен.

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

 <tex>\begin{array}{l l} S\rightarrow AB|a</tex>\\<tex> A\rightarrow b\end{array}.</tex> Если начать с проверки достижимостиВсе нетерминалы в этой грамматике достижимы. Однако, то все символы грамматики оказываются достижимыми. Если затем если удалить <tex>B</tex> как непорождающий символ, то останется грамматика с бесполезными символами нетерминал <tex>A</tex> и <tex>b</tex>станет недостижимым.