Утверждение. В эпсилон-свободной грамматике любой любой цикл является циклическим выводом

В эпсилон-свободной грамматике любой цикл является циклическим выводом

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

От противного. Пусть в эпсилон-свободной грамматике нашелся цикл, не являющийся циклическим выводом. Тогда в этом в выводе этого цикла есть применения правила вида:

$$B\Rightarrow \alpha C$$

где $\alpha \in {\Gamma }^{\ast }$

Цикл тогда выглядит следующим образом:

$$A{\Rightarrow }^{\ast }B\Rightarrow \alpha C{\Rightarrow }^{\ast }A$$

Длина цепочки $\alpha C>1$ То есть где-то в выводе длина цепочки должна уменьшится (в какой-то момент)

$$\alpha C{\Rightarrow }^{\ast }A$$

Так как грамматика контекстно-свободная уменьшить длину слова можно только при наличии в грамматике правил вида $D\Rightarrow ϵ$. То есть грамматика с необходимостью содержит хотя бы одно такое правило (не из аксиомы). Однако она является эпсилон-свободной и, следовательно, не может содержать таких правил. Получили противоречие