Регулярная грамматика

Материал из WEGA
Версия от 14:08, 26 июня 2009; KVN (обсуждение | вклад) (Создана новая страница размером Праволинейная грамматика <math>G=(N,\Sigma,P,S)</math> называется ''регулярной'' (или [[...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Праволинейная грамматика [math]\displaystyle{ G=(N,\Sigma,P,S) }[/math] называется регулярной (или автоматной), если

(1) все ее правила, за исключением [math]\displaystyle{ S \longrightarrow e }[/math], имеют вид [math]\displaystyle{ A\longrightarrow aB }[/math] или [math]\displaystyle{ A\longrightarrow a }[/math], где [math]\displaystyle{ B\in N }[/math], [math]\displaystyle{ a\in\Sigma }[/math],

(2) если [math]\displaystyle{ S\longrightarrow e }[/math] принадлежит [math]\displaystyle{ P }[/math], то [math]\displaystyle{ S }[/math] не встречается в правых частях правил.

Литература

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

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

[Касьянов-Поттосин].