153
правки
Изменения
Нет описания правки
{{Определение
|definition=
# Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части.
# Если на шаге 2 список больше не пополняется, то получен список всех порождающих нетерминалов грамматики, а все нетерминалы , не попавшие в него , являются непорождающими.
{{Определение
|definition=
Символ '''<tex>A</tex>''' называется '''недостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если '''<tex>A</tex>''' не появляется ни в одной выводимой цепочкенельзя вывести из стартового нетерминала.
}}
<tex>\Leftarrow</tex> Рассмотрим любой нетерминал <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> - не бесполезный.
}}
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
