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

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

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

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

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

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

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

Примеры

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

1. [math]\displaystyle{ S \rightarrow aSBC }[/math]
2. [math]\displaystyle{ S \rightarrow aBC }[/math]
3. [math]\displaystyle{ CB\rightarrow CZ }[/math]
4. [math]\displaystyle{ CZ \rightarrow WZ }[/math]
5. [math]\displaystyle{ WZ \rightarrow WC }[/math]
6. [math]\displaystyle{ WC \rightarrow BC }[/math]
7. [math]\displaystyle{ aB \rightarrow ab }[/math]
8. [math]\displaystyle{ bB \rightarrow bb }[/math]
9. [math]\displaystyle{ bC \rightarrow bc }[/math]
10. [math]\displaystyle{ cC \rightarrow cc }[/math]

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

[math]\displaystyle{ S }[/math]

[math]\displaystyle{ \Rightarrow_1 aSBC }[/math]

[math]\displaystyle{ \Rightarrow_1 a\boldsymbol{aSBC}BC }[/math]

[math]\displaystyle{ \Rightarrow_2 aa\boldsymbol{aBC}BCBC }[/math]

[math]\displaystyle{ \Rightarrow_3 aaaB\boldsymbol{CZ}CBC }[/math]

[math]\displaystyle{ \Rightarrow_4 aaaB\boldsymbol{WZ}CBC }[/math]

[math]\displaystyle{ \Rightarrow_5 aaaB\boldsymbol{WC}CBC }[/math]

[math]\displaystyle{ \Rightarrow_6 aaaB\boldsymbol{BC}CBC }[/math]

[math]\displaystyle{ \Rightarrow_3 aaaBBC\boldsymbol{CZ}C }[/math]

[math]\displaystyle{ \Rightarrow_4 aaaBBC\boldsymbol{WZ}C }[/math]

[math]\displaystyle{ \Rightarrow_5 aaaBBC\boldsymbol{WC}C }[/math]

[math]\displaystyle{ \Rightarrow_6 aaaBBC\boldsymbol{BC}C }[/math]

[math]\displaystyle{ \Rightarrow_3 aaaBB\boldsymbol{CZ}CC }[/math]

[math]\displaystyle{ \Rightarrow_4 aaaBB\boldsymbol{WZ}CC }[/math]

[math]\displaystyle{ \Rightarrow_5 aaaBB\boldsymbol{WC}CC }[/math]

[math]\displaystyle{ \Rightarrow_6 aaaBB\boldsymbol{BC}CC }[/math]

[math]\displaystyle{ \Rightarrow_7 aa\boldsymbol{ab}BBCCC }[/math]

[math]\displaystyle{ \Rightarrow_8 aaa\boldsymbol{bb}BCCC }[/math]

[math]\displaystyle{ \Rightarrow_8 aaab\boldsymbol{bb}CCC }[/math]

[math]\displaystyle{ \Rightarrow_9 aaabb\boldsymbol{bc}CC }[/math]

[math]\displaystyle{ \Rightarrow_{10} aaabbb\boldsymbol{cc}C }[/math]

[math]\displaystyle{ \Rightarrow_{10} aaabbbc\boldsymbol{cc} }[/math]

См. также

• JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата

Литература

• Кук Д., Бейз Г. Глава 8. Языки и грамматики // Компьютерная математика = Computer Mathematics. — М.: Наука. Физматлит, 1990. — 384 с. — ISBN 5-02-014216-6.