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

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

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

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

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

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

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

ПримерыПравить

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

1. $S\to <!--\; \to \; -->aSBC$$S\rightarrow aSBC$ 
2. $S\to <!--\; \to \; -->aBC$$S\rightarrow aBC$ 
3. $CB\to <!--\; \to \; -->CZ$$CB\rightarrow CZ$ 
4. $CZ\to <!--\; \to \; -->WZ$$CZ\rightarrow WZ$ 
5. $WZ\to <!--\; \to \; -->WC$$WZ\rightarrow WC$ 
6. $WC\to <!--\; \to \; -->BC$$WC\rightarrow BC$ 
7. $aB\to <!--\; \to \; -->ab$$aB\rightarrow ab$ 
8. $bB\to <!--\; \to \; -->bb$$bB\rightarrow bb$ 
9. $bC\to <!--\; \to \; -->bc$$bC\rightarrow bc$ 
10. $cC\to <!--\; \to \; -->cc$$cC\rightarrow cc$ 

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

$S$$S$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{1}aSBC$$\Rightarrow _{1}aSBC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{1}a\mathit{a}\mathit{S}\mathit{B}\mathit{C}BC$$\Rightarrow _{1}a{\boldsymbol {aSBC}}BC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{2}aa\mathit{a}\mathit{B}\mathit{C}BCBC$$\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{3}aaaB\mathit{C}\mathit{Z}CBC$$\Rightarrow _{3}aaaB{\boldsymbol {CZ}}CBC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{4}aaaB\mathit{W}\mathit{Z}CBC$$\Rightarrow _{4}aaaB{\boldsymbol {WZ}}CBC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{5}aaaB\mathit{W}\mathit{C}CBC$$\Rightarrow _{5}aaaB{\boldsymbol {WC}}CBC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{6}aaaB\mathit{B}\mathit{C}CBC$$\Rightarrow _{6}aaaB{\boldsymbol {BC}}CBC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{3}aaaBBC\mathit{C}\mathit{Z}C$$\Rightarrow _{3}aaaBBC{\boldsymbol {CZ}}C$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{4}aaaBBC\mathit{W}\mathit{Z}C$$\Rightarrow _{4}aaaBBC{\boldsymbol {WZ}}C$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{5}aaaBBC\mathit{W}\mathit{C}C$$\Rightarrow _{5}aaaBBC{\boldsymbol {WC}}C$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{6}aaaBBC\mathit{B}\mathit{C}C$$\Rightarrow _{6}aaaBBC{\boldsymbol {BC}}C$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{3}aaaBB\mathit{C}\mathit{Z}CC$$\Rightarrow _{3}aaaBB{\boldsymbol {CZ}}CC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{4}aaaBB\mathit{W}\mathit{Z}CC$$\Rightarrow _{4}aaaBB{\boldsymbol {WZ}}CC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{5}aaaBB\mathit{W}\mathit{C}CC$$\Rightarrow _{5}aaaBB{\boldsymbol {WC}}CC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{6}aaaBB\mathit{B}\mathit{C}CC$$\Rightarrow _{6}aaaBB{\boldsymbol {BC}}CC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{7}aa\mathit{a}\mathit{b}BBCCC$$\Rightarrow _{7}aa{\boldsymbol {ab}}BBCCC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{8}aaa\mathit{b}\mathit{b}BCCC$$\Rightarrow _{8}aaa{\boldsymbol {bb}}BCCC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{8}aaab\mathit{b}\mathit{b}CCC$$\Rightarrow _{8}aaab{\boldsymbol {bb}}CCC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{9}aaabb\mathit{b}\mathit{c}CC$$\Rightarrow _{9}aaabb{\boldsymbol {bc}}CC$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{10}aaabbb\mathit{c}\mathit{c}C$$\Rightarrow _{10}aaabbb{\boldsymbol {cc}}C$ 

${\Rightarrow <!--\; \Rightarrow \; -->}_{10}aaabbbc\mathit{c}\mathit{c}$$\Rightarrow _{10}aaabbbc{\boldsymbol {cc}}$ 

См. такжеПравить

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

ЛитератураПравить

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