65
правок
Изменения
Нет описания правки
|definition=
Символ '''<tex>A</tex>''' называется '''бесполезным''' в
КС-грамматике '''<tex>\Gamma</tex>''', если он не может встретиться в выводе слова из терминалов. То есть не существует порождения вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>, где <tex>w</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> - не бесполезный.
}}
{{Теорема
|id=th2
|statement=
Пусть <tex>G</tex> {{---}} КС-грамматика, и <tex>L(G)\ne\empty</tex>. Пусть <tex>G_1</tex> - грамматика, полученная с помощью следующих двух шагов:
1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>G_2</tex> {{---}} полученная в результате грамматика.
2) Удаляются все символы, недостижимые из <tex>G_2</tex>.
Тогда <tex>G_1</tex> не имеет бесполезных символов и <tex>L(G_1)=L(G)</tex>.
|proof=
Пусть <tex>X</tex> {{---}} оставшийся символ. Известно, что <tex>X\Rightarrow _G^* w</tex> для некоторой цепочки <tex>w</tex> из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\Rightarrow _{G_2}^* w</tex>.
Поскольку <tex>X</tex> не был удален на втором шаге, известно, что существует такие <tex>\alpha</tex> и <tex>\beta</tex>, для которых <tex>S\Rightarrow _{G_2}^* \alpha X\beta</tex>. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\Rightarrow _{G_1}^* \alpha X\beta</tex>.
Также известно, что каждый символ в цепочке <tex>\alpha X\beta</tex> достижим, поэтому каждый из них является порождающим в <tex>G_2</tex>. Порождение некоторой терминальной цепочки, например, <tex>\alpha X\beta\Rightarrow _{G_2}^* xwy</tex>, содержит только символы, достижимые из <tex>S</tex>, поскольку они достижимы из символов в цепочке <tex>\alpha X\beta</tex>. Таким образом, это порождение есть также порождение в <tex>G_1</tex>, то есть <tex>S\Rightarrow _{G_1}^* \alpha X\beta\Rightarrow _{G_1}^* xwy</tex>.
Итак, <tex>X</tex> полезен в <tex>G_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>G_1</tex> можно заключить, что <tex>G_1</tex> не имеет бесполезных символов.
<tex>L(G_1)\subseteq L(G)</tex>, так как при построении <tex>G_1</tex> из <tex>G</tex> символы и продукции только убирались. Докажем, что <tex>L(G_1)\supseteq L(G)</tex>. Если <tex>w\in L(G)</tex>, то <tex>S\Rightarrow _{G}^* w</tex>. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в <tex>G_1</tex> его также содержит. Таким образом, <tex>S\Rightarrow _{G_1}^* w</tex>, <tex>w\in L(G_1)</tex> и <tex>L(G)=L(G_1)</tex>.
}}
''Примечание:''
Эти шаги нельзя менять местами. Рассмотрим следующую грамматику:
<tex>S\rightarrow AB|A</tex>
<tex>A\rightarrow b</tex>
Если начать с проверки достижимости, то все символы грамматики оказываются достижимыми. Если затем удалить <tex>B</tex> как непорождающий символ, то останется грамматика с бесполезными символами <tex>A</tex> и <tex>b</tex>.
== Литература ==
* Джон ''ХопкрофтД., Раджив МотваниР., Джеффри УльманД. '' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
