Приведенные грамматики

#Пример

$S \to bAC | AcB$

$B \to bB$

$C \to C | d$

$A \to CB | bc$

Определение

Пусть G = ($\Sigma$, $Г$, $Р$, $S$) нетерминал $А$ $\in$ $Г$ наз-ся

1. производящим, если $A ⇒^_G u \in \Sigma^$
2. достижимым, если $S ⇒^*_G \alpha A \beta$

Грамматика $G$ наз-ся приведённой, если $\forall \ A \in Г$ является производящим и достижимым

Определение

Грамматика $G$ и $G'$ наз-ся эквивалентными, если они порождают один и тот же язык $L(G) = L(G')$.

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

<aside> 📌 $∀$ контекстносвободной грамматики $G$ существует эквивалентна ей приведенная.

</aside>

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

$G = (\Sigma, Г, P, S)$

1. Найдём все производящие символы:

   $Г_1' = \{ A \ \in \ Г | A ⇒_G u \in \Sigma^*\}$

   $….$

   $Г_i'$ $Г_{i+1}'$ $= \{B \in Г'| B \in Г' \ или \ B \to \alpha, \alpha \in(\Sigma \cup Г_i')^* \}$

   $Г'$ - множество производящих символов

   $G' = (\Sigma, Г', P', S)$

   в $P'$ лежат все правила, где все нетерминалы из $Г'$

2. Найдём достижимые в $Г'$

   $\hat{Г_1} = \{S\}$

   $....$

   $\hat{Г_i}$ - построено

   $\hat{Г_{i+1}} = \{A \in Г'| A \in \hat{Г_i}, B ⇒ \alpha AB, B \in \hat{Г_i} \}$

   Построим $\hat{Г}$ - достижимые в $Г'$

   $\hat{G} = (\Sigma, \hat{Г}, \hat{Р}, S)$

   В $\hat{P}$ все нетерминалы из $\hat{Г}$

   Теперь необходимо доказать, что: $L(\hat{G})=L(G)$ и $\hat{G}$ - приведённая

   В $\hat{Г}$ все достижимые по построению

   $A \ \in \ \hat{Г} \sube Г'$

   $⇒ A ⇒^*_{G'}$ $u$ ($A$ - достижимое в $\hat{G}$ )

   $S ⇒^*_{\v G}$ $\alpha AB$

   $⇒ S ⇒^_{G'} \alpha A \beta ⇒^_{G'} \alpha u \beta$ (все нетерминалы здесь достижимы)

   ( есть $u$ в грамматике $\hat{ G}$ $⇒ A$ -производящий)

   $L(\hat{ G}) ⊂ L(G)$

   $w \in L(G)$

   $S ⇒^*_G$ $w$ все нетерминалы достижимые и производящие $\hat{ G}$ этот же вывод есть в $\hat{ G}$

#Пример

1. Производящая

$\{C, A, S\}$