Регулярная аппроксимация КС-языков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(start)
(нет различий)

Версия 00:52, 19 января 2014


Определения

Определение:
Контекстно-свободная грамматика [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] .