Грамматика без e-правил: различия между версиями

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


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


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


Любая КС-грамматика может быть приведена к
Любая КС-грамматика может быть приведена к ''[[эквивалентные грамматики|эквивалентной]]'' ей без <math>e</math>-правил.
''эквивалентной'' ей без <math>e</math>-правил.
==Литература==
==Литература==
[Ахо-Ульман],  
[Ахо-Ульман],  


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

Текущая версия от 16:55, 8 октября 2009

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