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

Рекурсивный нетерминал (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]