205
правок
Изменения
м
→Алгоритм удаления ε-правил
}}
==Алгоритм удаления ε-правилиз грамматики ===== Поиск ε-порождающих нетерминалов ===:1) Если <tex>A \rightarrow \varepsilon</tex> — правило грамматики <tex>G</tex>, то <tex>A</tex> —<tex>\varepsilon</tex>-порождающий нетерминал.:2) Если <tex>B \rightarrow C_1C_2...C_k</tex> — правило грамматики <tex>G</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то <tex>B</tex> — <tex>\varepsilon</tex>-порождающий нетерминал. === Бла-бла ===
:''Вход''. КС-грамматика <tex> G=(N,\Sigma, P, S)</tex>.
:''Выход''. Эквивалентная КС-грамматика <tex> G'=(N',\Sigma, P', S') </tex> без <tex>\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>.<br/> Очевидно, что <tex>\varepsilon \in L(G)</tex> тогда и только тогда, когда <tex>\varepsilon \in L(G')</tex>.<br/> Таким образом, <tex>L(G)=L(G')</tex>.
}}
== Литература ==
* Ахо Альфред, Джеффри Ульман. Теория Синтаксического Анализа, Перевода и Компиляции. Том 1.
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
