Изменения

[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой'''(англ. ''self-embeded''), если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .

Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным'''(англ. ''recursive''), если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .

Нетерминалы <tex> A,B \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называются '''взаимно рекурсивными'''(англ. ''mutual recursive''), если <tex> \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</tex> .