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

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

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

Дана КС-грамматика. Построим эквивалентную ей приведенную грамматику

Поиск множества производящих нетерминалов ${\Gamma }^{\prime }$

Такое $i$ найдется, потому что $\Gamma$ конечно по определению грамматики. В худшем случае при каком-то ${\Gamma }^{\prime }$ совпадет с $\Gamma$

Построение новой грамматики $G^{\prime }$ на основе ${\Gamma }^{\prime }$

отфильтровали $P$ по требованию левой части из ${\Gamma }^{\prime }$

Поиск множества ${\Gamma }^{\prime \prime }$ достижимых нетерминалов в $G^{\prime }$

Такой $j$ найдется по причине того, что ${\Gamma }^{\prime }$ конечно по определению грамматики. В худшем случае ${\Gamma }^{\prime }={\Gamma }^{\prime \prime }$

Построение новой грамматики $G^{\prime \prime }$ на основе ${\Gamma }^{\prime \prime }$

отфильтровали $P$ по требованию левой части из ${\Gamma }^{\prime \prime }$

Доказательство эквивалентности $G^{\prime \prime }$ и $G$

(17) По построению $G^{\prime \prime }$: Возьмем $w\in L(G^{\prime \prime })$. Следовательно в грамматике $G^{\prime \prime }$ существует вывод $S{\Rightarrow }^{\ast }w$. Все правила, который участвуют в этом выводе - элементы исходного $P$ по построению ($P^{\prime \prime }\subseteq P^{\prime }\subseteq P$ ). Значит и в исходной грамматике существует такой же вывод → $w\in L(G)$

---

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

Вопросы

• 19 пункт