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

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

Визначення

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

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

Властивості

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

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

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

• $\alpha X\to \alpha \gamma$
• $X\beta \to \gamma \beta$
• $X\to \gamma$

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

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

Правила виводу КЗ-граматики не скорочують рядок в лівій частині. За винятком правила $S\to \epsilon$ для правил $w_1\to w_2$ виконується нерівність $\left|w_1\right|\le \left|w_2\right|$. Таким чином, КЗ-граматика завжди монотонна. КЗ- та монотонні граматики породжують однаковий клас мов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад

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

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

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

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

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

Див. також

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

Література

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