211
правок
Изменения
м
→Полезные и бесполезные нетерминалы
''Необходимость.'' Очевидно, т.к. недостижимые и непорождающие нетерминалы являются бесполезными.
''Достаточность.'' Рассмотрим любой нетерминал <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> {{---}} не бесполезный.
}}
== Алгоритм удаления бесполезных нетерминалов ==
