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

Контекстно-залежна граматика (скорочено КЗ-граматика) — формальна граматика типу 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^nb^nc^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