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

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


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


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

Текущая версия от 13:32, 15 декабря 2010

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