211
правок
Изменения
м
→Порождающие и непорождающие нетерминалы
Очевидно, что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правойчасти, части уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}
== Достижимые и недостижимые нетерминалы ==
