Изменения
Нет описания правки
== Используемые определения ==
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами'''(''<tex>\varepsilon</tex> rule'').
}}
{{Определение
|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим'''(''<tex>\varepsilon</tex>-generating''), если <tex>A \Rightarrow^* \varepsilon</tex>.
}}
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
}}
=== Время работы алгоритма ===
Рассмотрим грамматику:
<tex> \Gamma =
\begin{array}{l l}
S\rightarrow T_1 T_2 T_3 ... T_n\\
T_1\rightarrow t_1|\varepsilon\\
T_2\rightarrow t_2|\varepsilon\\
...\\
T_n\rightarrow t_n|\varepsilon
\end{array}
</tex>.<br>
<tex>\left| \Gamma \right| = O(n)</tex>. Из нетерминала <tex>S</tex> можно вывести <tex>2^n</tex> сочетаний нетерминалов <tex>T_i</tex>. Таким образом в худшем случае алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>.<br>
Однако если в грамматике устранены [[Удаление_длинных_правил_из_грамматики|длинные правила]], то алгоритм будет работать за <tex>O(\left| \Gamma \right|)</tex> и добавит в грамматику <tex>O(\left| \Gamma \right|)</tex> новых правил длинны <tex>O(1)</tex>.
=== Пример ===
Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2...C_k</tex>, где каждый нетерминал <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}
=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.
=== Пример ===
Таким образом <tex>\varepsilon</tex>-порождающими нетерминалами являются <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>S</tex>.
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
== Литература ==
