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

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

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

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

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

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

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

Примеры

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

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

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

${\displaystyle S}$

${\displaystyle \Rightarrow _{1}aSBC}$

${\displaystyle \Rightarrow _{1}a{\boldsymbol {aSBC}}BC}$

${\displaystyle \Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC}$

${\displaystyle \Rightarrow _{3}aaaB{\boldsymbol {CZ}}CBC}$

${\displaystyle \Rightarrow _{4}aaaB{\boldsymbol {WZ}}CBC}$

${\displaystyle \Rightarrow _{5}aaaB{\boldsymbol {WC}}CBC}$

${\displaystyle \Rightarrow _{6}aaaB{\boldsymbol {BC}}CBC}$

${\displaystyle \Rightarrow _{3}aaaBBC{\boldsymbol {CZ}}C}$

${\displaystyle \Rightarrow _{4}aaaBBC{\boldsymbol {WZ}}C}$

${\displaystyle \Rightarrow _{5}aaaBBC{\boldsymbol {WC}}C}$

${\displaystyle \Rightarrow _{6}aaaBBC{\boldsymbol {BC}}C}$

${\displaystyle \Rightarrow _{3}aaaBB{\boldsymbol {CZ}}CC}$

${\displaystyle \Rightarrow _{4}aaaBB{\boldsymbol {WZ}}CC}$

${\displaystyle \Rightarrow _{5}aaaBB{\boldsymbol {WC}}CC}$

${\displaystyle \Rightarrow _{6}aaaBB{\boldsymbol {BC}}CC}$

${\displaystyle \Rightarrow _{7}aa{\boldsymbol {ab}}BBCCC}$

${\displaystyle \Rightarrow _{8}aaa{\boldsymbol {bb}}BCCC}$

${\displaystyle \Rightarrow _{8}aaab{\boldsymbol {bb}}CCC}$

${\displaystyle \Rightarrow _{9}aaabb{\boldsymbol {bc}}CC}$

${\displaystyle \Rightarrow _{10}aaabbb{\boldsymbol {cc}}C}$

${\displaystyle \Rightarrow _{10}aaabbbc{\boldsymbol {cc}}}$

См. также

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

Литература

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