Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
}}
Очевидно, что если и только если все нетерминальные символы нетерминалы правой части являются порождающими, то порождающим является и символнетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.
Докажем, что после выполнения второго шага не могут появиться новые непорождающие нетерминалы.
Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> конечной цепочки терминалов, то было удалено хотя бы какое-то одно правило из этого вывода. Возьмем первое удалённое правило <tex>B\rightarrow\alpha</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.
