Грамматика без е-правил

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

(1) [math]\displaystyle{ P }[/math] не содержит [math]\displaystyle{ e }[/math]-правил, т.е. правил вида [math]\displaystyle{ A \longrightarrow e }[/math], где [math]\displaystyle{ A \in N }[/math];

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

Любая КС-грамматика может быть приведена к эквивалентной ей без [math]\displaystyle{ e }[/math]-правил.

Литература

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

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