65
правок
Изменения
Нет описания правки
<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> - не бесполезный.
}}
{{Теорема
|id=th2
|statement=
Пусть <tex>G</tex> {{---}} КС-грамматика, и <tex>L(G)\ne\emptyvarnothing</tex>. Пусть <tex>G_1</tex> - грамматика, полученная с помощью следующих двух шагов:
1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>G_2</tex> {{---}} полученная в результате грамматика.
