Рекурсивный нетерминал: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Рекурсивный нетерминал''' (''Recursive nonterminal symbol'') - ''нетерминал'' <math>A</math> ''конт...) |
(нет различий)
|
Версия от 14:49, 21 января 2010
Рекурсивный нетерминал (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]