Теорема. Об эпсилон-свободной грамматике

Для любой Контекстно-свободной грамматики существует эквивалентная ей эпсилон-свободная грамматика

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

Построение требуемой грамматики

Полагаем, что данная грамматика приведена. Если нет, используем алгоритм из теоремы

Построим для данной грамматики множество аннулирующих нетерминалов $Ann(G)$, используя алгоритм.

(1) можно считать по теореме, Упр 1: ${⪰}_G$ - частичный порядок так как:

1. Рефлексивность: стираем пустое множество, получаем то же слово
2. Антисимметричность: Не можем “восстанавливать” исходное слово по слову, у которого стерли нетерминалы
3. Транзитивность: Стереть можем сначала одну часть, потом другую, что эквивалентно стиранию сразу обоих частей (все равно подмножество $Ann(G)$) Упр 2: Так как нетерминалы, которые стираются из $Ann(G)$, то из них существует вывод в $ϵ$. Применим этот вывод для каждого нетерминала, который стираем у $\alpha$, получим требуемый вывод $\beta$ Упр 3: В слове $\alpha$ $n$ нетерминалов. Обозначим их $\{A_i{\}}_{i=1}^n,A_i\in Ann(G),$. То есть $\alpha ={\alpha }_0{A}_0{\alpha }_2{A}_2\dots {\alpha }_i{A}_i\dots {\alpha }_n{A}_n{\alpha }_{n+1},{\alpha }_i\in ((\Gamma \setminus Ann(G))\cup \Sigma {)}^{\ast },i=1,\dots ,n$ . По определению ${⪰}_G$ можем стирать любое подмножество. То есть всего комбинаций для стирания $2^n$ (мощность булеана множества)

(3) Приведенная грамматика строится по алгоритму из теоремы

Доказательство, что построенная грамматика является $ϵ$-свободной

Получили противоречие, т.к. правила вида $B\Rightarrow ϵ$ нет в построенной грамматике по п.2

Доказательство, что построенная грамматика эквивалентна исходной

Покажем, что $L(G^{\prime \prime })=L(G)$

$L(G^{\prime \prime })\subseteq L(G)$

(9) Доказываем, что если в $G^{\prime \prime }$ есть непосредственный вывод $\alpha {\Rightarrow }_{G^{\prime \prime }}\beta$, то в исходной есть просто вывод $\alpha {\Rightarrow }_G^{\ast }\beta$, $\alpha \ne ϵ,\beta \ne ϵ$

$L(G)\subseteq L(G^{\prime \prime })$

---

Связанные теоремы/определения

• Контекстно-свободная грамматика
• Эпсилон-свободная грамматика
• Приведенная грамматика
• Теорема. Существование эквивалентной приведенной грамматики для любой контекстно-свободной грамматики