Определение

$\varepsilon \ -$ свободной грамматика G наз-ся ацикличной, если $А \not\rArr^+ A$

#Пример

$S \to aBa | B$

$B \to b|C$

$A \to C|a$

$C \to A | bB$

Лемма (содержит алгоритм удаления)

<aside> 📌 Пусть в грамматике G есть правила $A_1 \to A_2, A_2 \to A_3 ... A_k \to A_1$ Тогда грамматка G наз-ся отрицанием индексов и удаляются $А \to A$ эквивалентна G

</aside>

$L(G) \ \ L(G')$ $w \ \in \ L(G)$ $S \rArr^_G w$ стёрли индекс $S \rArr^_G w \rArr w \ \in \ L(G')$

Обратно: $S \rArr_{G'} w$ $S \rArr^_G \alpha A \beta \rArr \alpha \eta \beta \rArr^ w$ $A \to \eta$ $\exist A_i \to \eta \in G$ Пусть в G $S \rArr^* \alpha A_j \beta \rArr^_G \alpha A_i \beta \rArr^ \alpha \eta \beta \rArr^* w \rArr w \in L(G)$

Теорема

<aside> 📌 Любая $\varepsilon$ - свобоная грамматика эквивалентна ацикличной

</aside>