Контекстно-зависимая грамматика

Контекстно-зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами.

Частным случаем формальной грамматики так же является контекстно-свободная грамматика.

Язык, который может быть задан КЗ-грамматикой, называется контекстно-зависимым языком или КЗ-языком.

Формальное определение

Формальная грамматика G=(N, T, I, P) является контекстно-зависимой, если все правила P имеют вид: αAβ → αωβ

где A ∈ N (то есть одиночный нетерминальный символ), ω ∈ (N ∪ T)⁺ (то есть непустая цепочка, состоящая из терминальных и/или нетерминальных символов), α, β ∈ (N ∪ T)* (то есть любая цепочка, состоящая из терминальных и/или нетерминальных символов).

Примеры

Следующая граматика задает контекстно-зависимый язык $\{ a^n b^n c^n : n \ge 1 \}$:

1. $S \rightarrow aSBC$
2. $S \rightarrow aBC$
3. $CB \rightarrow HB$
4. $HB \rightarrow HC$
5. $HC \rightarrow BC$
6. $aB \rightarrow ab$
7. $bB \rightarrow bb$
8. $bC \rightarrow bc$
9. $cC \rightarrow cc$

Так выглядит цепочка порождения aaa bbb ccc:

$S$

$\Rightarrow_1 aSBC$

$\Rightarrow_1 a\boldsymbol{aSBC}BC$

$\Rightarrow_2 aa\boldsymbol{aBC}BCBC$

$\Rightarrow_3 aaaB\boldsymbol{HB}CBC$

$\Rightarrow_4 aaaB\boldsymbol{HC}CBC$

$\Rightarrow_5 aaaB\boldsymbol{BC}CBC$

$\Rightarrow_3 aaaBBC\boldsymbol{HB}C$

$\Rightarrow_4 aaaBBC\boldsymbol{HC}C$

$\Rightarrow_5 aaaBBC\boldsymbol{BC}C$

$\Rightarrow_3 aaaBB\boldsymbol{HB}CC$

$\Rightarrow_4 aaaBB\boldsymbol{HC}CC$

$\Rightarrow_5 aaaBB\boldsymbol{BC}CC$

$\Rightarrow_6 aa\boldsymbol{ab}BBCCC$

$\Rightarrow_7 aaa\boldsymbol{bb}BCCC$

$\Rightarrow_7 aaab\boldsymbol{bb}CCC$

$\Rightarrow_8 aaabb\boldsymbol{bc}CC$

$\Rightarrow_9 aaabbb\boldsymbol{cc}C$

$\Rightarrow_9 aaabbbc\boldsymbol{cc}$