Рекурсивный нетерминал

Материал из WikiGrapp
Версия от 14:49, 21 января 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Рекурсивный нетерминал''' (''Recursive nonterminal symbol'') - ''нетерминал'' <math>A</math> ''конт...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Рекурсивный нетерминал (Recursive nonterminal symbol) - нетерминал [math]\displaystyle{ A }[/math] контекстно-свободной грамматики [math]\displaystyle{ G=(N,\Sigma,P,S) }[/math], если [math]\displaystyle{ A\Longrightarrow^+\alpha A\beta }[/math] для некоторых [math]\displaystyle{ \alpha }[/math] и [math]\displaystyle{ \beta }[/math]. Если [math]\displaystyle{ \alpha =e }[/math], то [math]\displaystyle{ A }[/math] называется леворекурсивным. Аналогично, если [math]\displaystyle{ \beta =e }[/math], то [math]\displaystyle{ A }[/math] называется праворекурсивным.

Грамматика [math]\displaystyle{ G }[/math] называется леворекурсивной (соответственно праворекурсивной), если в [math]\displaystyle{ G }[/math] имеется хотя бы один леворекурсивный (соответственно праворекурсивный) нетерминал. Грамматика, в которой рекурсивны все нетерминалы, кроме, быть может, начального символа, называется рекурсивной.

Литература

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

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