Изменения

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

Рассматривая правила грамматики, можно сделать вывод, что если и только если все нетерминальные символы правой части являются производящимипорождающими, то производящим порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих непорождающих символов в следующем виде:

# Если на шаге 2 список больше не пополняется, то получен список всех производящих порождающих нетерминалов грамматики, а все нетерминалы не попавшие в него являются непроизводящиминепорождающими.

КС-грамматике '''<tex>\Gamma</tex>''', если он является недостижимым или непроизводящимне может встретиться в выводе слова из терминалов.

Исключить бесполезные символы из грамматики можно удаляя правилаГрамматика <tex>\Gamma</tex> не содержит бесполезных символов '''тогда и только тогда, содержащие вначале непроизводящиекогда''' она не содержит ни недостижимых символов, а затем недостижимые символыни непорождающих.

Любой терминальный символ является генерирующим<tex>\Rightarrow</tex> Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными.Пусть <tex>\Leftarrow</tex> Рассмотрим любой нетерминал <tex>A \rightarrow </tex>. Так как он достижимый, существуют <tex>\alpha</tex> и известно<tex>\beta</tex>, такие, что <tex>S \Rightarrow ^* \alphaA \beta</tex> состоит только . Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из генерирующих символовтерминалов. Значит, тогда существует <tex>A\theta \in \Sigma ^ *</tex> - генерирующий символ.Если : <tex>S \Rightarrow ^* \alpha = A \beta \Rightarrow ^* \epsilontheta</tex>, тогда и <tex>A</tex> также генерирующий символ- не бесполезный.