ε - свободные грамматики

Определение

Грамматика $G = (\Sigma, Г, P, S)$ наз-ся ε-свободной, если в $G$ либо нет $A \to ε$ (аннулирующие), либо если есть $S \to ε$, тогда $S$ не встречается вправых частях правил вывода.

Теорема(доказательство содержит алгоритм)

<aside> 📌 Для любой контекстносвободной грамматики существует эквивалентная ей ε-свободная.

</aside>

Доказательство:

$А_{nn}(G)$ - множество анулирующих символов

$A \in A_{nn}(G) | A ⇒^* \varepsilon$

$Г_1 = \{ A \in Г | A \to ε \}$

$…$

$Г_{i+1} = \{ A \in Г | A \in Г_i, \ \text{либо} \ А \to \alpha \in Г^*_i \}$

$A \to \beta \in P_G$

$\alpha Δ \beta$, если $\alpha \not = \varepsilon$, $\alpha$ получается из $\beta$ удалением анулирующих символов.

Строим $G' = (\Sigma, Г, P', S)$

Из $P'$ удаляем все правила вида $A \to ε$

добавляем $∀ A \to B$ все $A \to \alpha$, $\alpha Δ \beta$

Если $S \in A_{nn}(G)$

Новая аксиома $S' \to ε | S$

Доказываем эквивалентность:

$S \rArr^*_G w$

$S ⇒^_G \ \alpha A \gamma \ ⇒_G \ \alpha \delta_1 B \delta_2 \gamma \ ⇒^_G \ \alpha \delta_1 \delta_2 \gamma \ ⇒^* w$

$S ⇒^{G’} \ \alpha A \gamma ⇒{G'} \alpha \delta_1 \delta_2 \gamma ⇒^_{G'} w$

#Пример

$S \to ABC$ $S \to ABC | BC | AC | AB | A | B | C$

$A \to aAb$ $A \to aAb | ab$

$\sout{A \to ε}$

$B \to bB$ $B \to bB | b$

$\sout{B \to ε}$

$C \to CS$ $C \to cS, C \to c$

$\sout{C \to ε}$ $S' \to ε| S$

$A_{nn}(G) = \{A, B, C, S\}$