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

Материал из WEGA
Перейти к навигации Перейти к поиску

Грамматика без [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]-правил.

Литература

[Ахо-Ульман],

[Касьянов/95]