Изменения

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

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

Символ '''Нетерминал <tex>A</tex>''' называется '''недостижимымдостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если строку, содержащую '''существует порождение <tex>S \Rightarrow^* \alpha A\beta</tex>. Иначе он называется '''недостижимым''', нельзя вывести из стартового нетерминала.

Рассматривая правила грамматики, можно заметить Очевидно, что если нетерминал в левой части правила является достижимым , то и все символы нетерминалы правой части являются достижимыми. Это свойство правил является основой Найти недостижимые нетерминалы можно с помощью следующей процедуры выявления недостижимых символов, которую можно записать так: .# Образовать одноэлементный списокВозьмём множество, состоящий состоящее из начального символа единственного элемента: <tex>\lbrace S \rbrace</tex>.# Если найдено правило, левая часть в левой части которого уже имеется стоит нетерминал, содержащийся в спискемножестве, то включить добавить в список множество все символы, содержащиеся в его нетерминалы из правой части. # Если на шаге 2 новые нетерминалы в список больше не добавляютсямножество изменилось, то получен список повторить шаг 2.# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в списокнего, являются недостижимыми.

Символ '''Нетерминал <tex>A</tex>''' называется '''бесполезнымполезным''' в КС-грамматике '''<tex>\Gamma</tex>''', если он не может встретиться участвовать в выводе слова из терминалов. То , то есть не существует порождения порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>, где <tex>w</tex> {{---}} строка терминалов. Иначе он называется '''бесполезным'''.

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

<tex>\Rightarrow</tex> <br />Очевидно, т.к. недостижимые и непорождающие символы нетерминалы являются бесполезными. <tex>\Leftarrow</tex> <br />Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижимыйдостижим, существуют <tex>\alpha</tex> и <tex>\beta</tex>, такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой символ нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{--- }} не бесполезный.