Контекстно-залежна граматика

Контекстно-залежна граматика (скорочено КЗ-граматика) — формальна граматика типу 1 в ієрархії Чомскі. Особливість КЗ граматик в тому, що правила виводу здійснюють заміну нетермільнального символу лише у визначеному контексті.

Визначення

Контекстно-залежна граматика, це формальна граматика $G=(N,T,P,S)$ де

• $N$ — множина нетермінальних символів
• $T$ — множина термінальних символів
• $S\in N$ — початковий символ
• $P$ — правила виводу виду $\alpha X\beta \rightarrow \alpha \gamma \beta$ або $S\rightarrow \varepsilon$, за умов:
  • $\alpha ,\beta \in (N\cup T)^{*}$
  • $X\in N$
  • $\gamma \in (N\cup T)^{+}$
  • $S$ відсутнє в правій частині правил виводу

Властивості

За єдиним винятком, визначені правила виводу мають вид $\alpha X\beta \rightarrow \alpha \gamma \beta$ та $\gamma \neq \varepsilon$.

Це означає, що нетермінальний символ $X$ в контексті $\alpha$ та $\beta$ буде замінено на $\gamma$. Але, в той час, як довжина $\gamma$ має бути не менше за одиницю, і $\alpha$ і $\beta$ можуть бути порожніми.

Наступні приклади крайніх випадків відповідають визначенню:

• $\alpha X\rightarrow \alpha \gamma$
• $X\beta \rightarrow \gamma \beta$
• $X\rightarrow \gamma$

Аби зробити можливим роботу з порожнім словом, дозволяють правило $S\rightarrow \varepsilon$, за умови відсутності $S$ в правій частині правил виводу.

Контекстно-залежні та монотонні граматики

Правила виводу КЗ-граматики не скорочують рядок в лівій частині. За винятком правила $S\rightarrow \varepsilon$ для правил $w_{1}\rightarrow w_{2}$ виконується нерівність $\left|w_{1}\right|\leq \left|w_{2}\right|$. Таким чином, КЗ-граматика завжди монотонна. КЗ- та монотонні граматики породжують однаковий клас мов.

Деякі автори наводять визначення КЗ-граматик в контексті монотонних. Правила виводу виду $\alpha X\beta \rightarrow \alpha \gamma \beta$ розглядають як типову або канонічну форму правил КЗ-граматик.

Нормальні форми

Кожній КЗ-граматиці відповідає граматика в нормальній формі Куроди з правилами виводу виду:

• $A\rightarrow a$
• $A\rightarrow B$
• $A\rightarrow BC$
• $AB\rightarrow CD$

Граматика в нормальній формі Куроди монотонна, але не завжди контекстно-залежна.

КЗ нормальна форма подовжуюча, якщо має правила виду:

• $A\rightarrow a$
• $A\rightarrow BC$
• $AB\rightarrow AC$

Кожній КЗ граматиці відповідає подовжувальна граматика в нормальній формі.

Альтернативне позначення

Мовознавці використовують інші позначення для правил виводу.. Правила підставляння визначають аналогічно правилам виводу, а в правій частині вказують контекст, в якому можна застосувати правило: $X\rightarrow \gamma \;/\alpha \_\!\_\!\_\!\_\beta /$

Мови породжені КЗ-граматиками

Контекстно-залежні граматики породжують контекстно-залежні мови. Тобто, кожна КЗ граматика породжує КЗ мову, і для кожної КЗ мови існує КЗ граматика, що її породжує.

Контекстно-залежні мови можна розпізнати недетермінованою лінійно-обмеженою машиною Тюринга (недетермінована машина Тюринга зі стрічкою обмеженої довжини).

Визначення приналежності слва мові ($x\in L$) для КЗ-мов розв'язувана.

Приклад

Контекстно-залежну мову $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ слів, які складаються з однакової кількості літер a за якими йдуть b та c, визначають наступною КЗ граматикою:

$G=(N,T,P,S)$ з термінальними символами $T=\{a,b,c\}$ та нетермінальними $N=\{B,C,H,S\}$ та правилами виводу $P:$

1. $S\rightarrow aSBC\mid aBC$
2. $CB\rightarrow HB$
3. $HB\rightarrow HC$
4. $HC\rightarrow BC$
5. $aB\rightarrow ab$
6. $bB\rightarrow bb$
7. $bC\rightarrow bc$
8. $cC\rightarrow cc$

Слово $aabbcc\in L$ можна отримати таким чином (підкреслено контекст, в якому відбувається заміна):

${\begin{array}{l}{\underline {S}}\Rightarrow _{1}a{\underline {S}}BC\Rightarrow _{1}aaB{\underline {CB}}C\Rightarrow _{2}aaB{\underline {HB}}C\\\Rightarrow _{3}aaB{\underline {HC}}C\Rightarrow _{4}a{\underline {aB}}BCC\Rightarrow _{5}aa{\underline {bB}}CC\\\Rightarrow _{6}aab{\underline {bC}}C\Rightarrow _{7}aabb{\underline {cC}}\Rightarrow _{8}aabbcc\end{array}}$

Див. також

• Граматика залежностей

Література

• Grzegorz Rozenberg, Arto Salomaa. Handbook of Formal Languages: Word, Language, Grammar. — Springer, 1997. — Т. Vol.1. — ISBN 9783540604204.
• Katrin Erk, Lutz Priese. Theoretische Informatik: Eine umfassende Einführung. — Springer, 2008. — ISBN 9783540763192.