если есть желание послушать: ссылка

Порождающая грамматика

Определение

Порождающая грамматика

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

$\Sigma$ - множество букв (алфавит): непустой, терминал ($a,\ b, \ c, \ d \ \epsilon\ \Sigma$)

$Г$ - алфавит: нетерминалов ($S, \ T,\ A \ \epsilon \ Г$ )

$S \ \epsilon \ Г$ - аксиома грамматики

$P$ - множество правил вывода

$\beta \ \epsilon \ (\Sigma \ ∪ \ Г)^*$

$\alpha \ \epsilon \ (\Sigma \ ∪ \ Г)^*$ - отличается от предыдущего тем, что должен иметь хотя бы один нетерминал

Определение

Непосредственным выводом из цепочки (строки) $\gamma_1$ , цепочки (строки) $\gamma_2$ c помощью правила вывода $\alpha → \beta$ наз-ся

$\gamma_1 = \delta_1 \alpha \delta_2$

$\gamma_2 = \delta_1 \beta \delta_2$

$\delta_1 \alpha \delta_2 ⇒ \delta_1 \beta \delta_2$

#Пример

$\Sigma = \{ a, b \}$ $Г = \{S, A\}$

$P = \{S \to aaAb| ε, aA \to S \}$, где знак “|” обозначает альтернативу

$S ⇒ aaAb ⇒ aSb ⇒ ab$

                       $aSb ⇒ aaaAbb ⇒ a^2Sb^2 ⇒ a^2b^2$

Язык, порожденный G

Определение

Цепочка $\gamma_2$ выводится из $\gamma_1$ в грамматику $G$ $\gamma_1 ⇒^*_G \gamma_2$ , если существует $η_1 ….. η_n$ $\gamma_1 = η_1 ⇒ η_2 ⇒…. ⇒ η_n = \gamma_2$

Определение

$G = (\Sigma, Г, P, S)$ - грамматика

Языком порождаемым грамматикой G наз-ся $L(G) = \{w \in \Sigma^* | S ⇒^*_G w \}$ (вывод цепочки $w$)

#Пример

$S \to AB$

$A \to aA|ε$

$B \to bB|ε$

$S ⇒ AB ⇒ aAB ⇒ aB ⇒ a$

Левосторонний вывод, при котором заменяются самый левый нетерминалы.