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

Контекстно зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 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\to aSBC$
2. $S\to aBC$
3. $CB\to CZ$
4. $CZ\to WZ$
5. $WZ\to WC$
6. $WC\to BC$
7. $aB\to ab$
8. $bB\to bb$
9. $bC\to bc$
10. $cC\to cc$

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

$S$

${\Rightarrow }_{1}aSBC$

${\Rightarrow }_{1}a𝒂𝑺𝑩𝑪BC$

${\Rightarrow }_{2}aa𝒂𝑩𝑪BCBC$

${\Rightarrow }_{3}aaaB𝑪𝒁CBC$

${\Rightarrow }_{4}aaaB𝑾𝒁CBC$

${\Rightarrow }_{5}aaaB𝑾𝑪CBC$

${\Rightarrow }_{6}aaaB𝑩𝑪CBC$

${\Rightarrow }_{3}aaaBBC𝑪𝒁C$

${\Rightarrow }_{4}aaaBBC𝑾𝒁C$

${\Rightarrow }_{5}aaaBBC𝑾𝑪C$

${\Rightarrow }_{6}aaaBBC𝑩𝑪C$

${\Rightarrow }_{3}aaaBB𝑪𝒁CC$

${\Rightarrow }_{4}aaaBB𝑾𝒁CC$

${\Rightarrow }_{5}aaaBB𝑾𝑪CC$

${\Rightarrow }_{6}aaaBB𝑩𝑪CC$

${\Rightarrow }_{7}aa𝒂𝒃BBCCC$

${\Rightarrow }_{8}aaa𝒃𝒃BCCC$

${\Rightarrow }_{8}aaab𝒃𝒃CCC$

${\Rightarrow }_{9}aaabb𝒃𝒄CC$

${\Rightarrow }_{10}aaabbb𝒄𝒄C$

${\Rightarrow }_{10}aaabbbc𝒄𝒄$

См. также

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

Литература

• Шаблон:Книга