188
правок
Изменения
Нет описания правки
== Полезные и бесполезные нетерминалы ==
===Описание===
{{Определение
|definition=
}}
=== Алгоритм удаления бесполезных нетерминалов ===Алгоритм состоит из двух этапов:
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.
Достаточность данных действий следует из доказанной выше теоремы.
Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.
Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.
}}
=== Пример ===
