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

Материал из WEGA
Версия от 12:15, 8 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером Грамматика без <math>e</math>-правил (''e-Free grammar'') - КС-грамматика <math>G</math>=<math>(N</math>,<...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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