188
правок
Изменения
→Достижимые и недостижимые нетерминалы
== Достижимые и недостижимые нетерминалы ==
===Описание===
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' (англ. ''reachable'') в [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматике]] <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым''' (англ. ''unreachable'').
}}
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.# Если на шаге 2 множество изменилось, повторить шаг 2.# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
{{Лемма
|statement=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}
===Алгоритм===
'''Шаг 0.''' Множество достижимых нетерминалов состоит из единственного элемента: <tex>\lbrace S \rbrace</tex>.<br>
'''Шаг 1.''' Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.<br>
'''Шаг 2.''' Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
=== Время работы алгоритма ===
