Просмотр кода страницы Грамматика без е-правил

'''Грамматика без <math>e</math>-правил''' (''[[e-Free grammar]]'') — [[КС-Грамматика|КС-грамматика]] <math>G</math>=<math>(N</math>,<math>\Sigma</math>, <math>P</math>,<math>S)</math>, для которой справедливо одно из следующих правил:

(1) <math>P</math> не содержит ''<math>e</math>-правил'', т.е. правил вида
<math>A \longrightarrow e</math>, где <math>A \in N</math>;

(2) в <math>P</math> есть точно одно
<math>e</math>-правило <math>S \longrightarrow e</math> и <math>S</math> не встречается
в правых частях остальных правил из <math>P</math>.

Любая КС-грамматика может быть приведена к
''эквивалентной'' ей без <math>e</math>-правил.

==Литература==
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.

* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений.  — Новосибирск: НГУ, 1995.