| Определение: |
| Контекстно-свободная грамматика [math] G = \langle N, \Sigma, P, S \rangle[/math] называется самоприменимой, если [math] \exists A \in N: A \Rightarrow^* \alpha A \beta[/math], [math] \alpha \neq \varepsilon \land \beta \neq \varepsilon [/math] . |
| Определение: |
| Нетерминал [math] A \in N[/math] в грамматике [math] G = \langle N, \Sigma, P, S \rangle[/math] называется рекурсивным, если [math] \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta[/math] . |
| Определение: |
| Нетерминалы [math] A,B \in N[/math] в грамматике [math] G = \langle N, \Sigma, P, S \rangle[/math] называются взаимно рекурсивными, если [math] \exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2[/math] . |
