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

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

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

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

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

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

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

Примеры

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

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

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

<math>S</math>

<math>\Rightarrow_1 aSBC</math>

<math>\Rightarrow_1 a\boldsymbol{aSBC}BC </math>

<math>\Rightarrow_2 aa\boldsymbol{aBC}BCBC </math>

<math>\Rightarrow_3 aaaB\boldsymbol{HB}CBC </math>

<math>\Rightarrow_4 aaaB\boldsymbol{HC}CBC </math>

<math>\Rightarrow_5 aaaB\boldsymbol{BC}CBC </math>

<math>\Rightarrow_3 aaaBBC\boldsymbol{HB}C </math>

<math>\Rightarrow_4 aaaBBC\boldsymbol{HC}C </math>

<math>\Rightarrow_5 aaaBBC\boldsymbol{BC}C </math>

<math>\Rightarrow_3 aaaBB\boldsymbol{HB}CC </math>

<math>\Rightarrow_4 aaaBB\boldsymbol{HC}CC </math>

<math>\Rightarrow_5 aaaBB\boldsymbol{BC}CC </math>

<math>\Rightarrow_6 aa\boldsymbol{ab}BBCCC </math>

<math>\Rightarrow_7 aaa\boldsymbol{bb}BCCC </math>

<math>\Rightarrow_7 aaab\boldsymbol{bb}CCC </math>

<math>\Rightarrow_8 aaabb\boldsymbol{bc}CC </math>

<math>\Rightarrow_9 aaabbb\boldsymbol{cc}C </math>

<math>\Rightarrow_9 aaabbbc\boldsymbol{cc} </math>