Грамматика без e-правил: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером Грамматика без <math>e</math>-правил (''e-Free grammar'') - КС-грамматика <math>G</math>=<math>(N</math>,<...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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]