188
правок
Изменения
→Порождающие и непорождающие нетерминалы
== Порождающие и непорождающие нетерминалы ==
===Описание===
{{Определение
|definition=
[[Формальные_грамматики|Нетерминал]] <tex>A</tex> называется '''порождающим''' (англ. ''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры:# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.# Если на шаге 2 множество изменилось, повторить шаг 2.# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
{{Лемма
|statement=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}
===Алгоритм===
'''Шаг 0'''. Множество порождающих нетерминалов пустое.<br>
'''Шаг 1'''. Находим правила, не содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.<br>
'''Шаг 2'''. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавим в множество нетерминалы, стоящие в его левой части. <br>
'''Шаг 3'''. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>
В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
=== Время работы алгоритма ===
