Изменения
Нет описания правки
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим'''(''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}
=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако, если в грамматике устранены [[Удаление_длинных_правил_из_грамматики|длинные правила]], то используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.
=== Пример ===
S\rightarrow Ac\\
A\rightarrow SD\\
D\rightarrow aD\\
A\rightarrow a
\end{array}
</tex>
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.
# Добавим в множество нетеминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>BA</tex>, который есть в множестве, и терминал <tex>c</tex>.
# После следуещего обхода правил из грамматики множество не изменится.
# Теперь удалим правило правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как оно они содержит в правой части нетерминалнетерминалы, которого которых нет в полученном множестве.
== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' (''reachable'') в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''(''unreachable'').
}}
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
{{Лемма
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}
=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Обход_в_глубину,_цвета_вершин|обход в глубину]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.
=== Пример ===
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' (''useful'') в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''(''useless'').
}}
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
== Литература ==
