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

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

Визначення

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

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

Властивості

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

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

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

• ${\displaystyle \alpha X\rightarrow \alpha \gamma }$
• ${\displaystyle X\beta \rightarrow \gamma \beta }$
• ${\displaystyle X\rightarrow \gamma }$

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

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

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

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

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

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

• ${\displaystyle A\rightarrow a}$
• ${\displaystyle A\rightarrow B}$
• ${\displaystyle A\rightarrow BC}$
• ${\displaystyle AB\rightarrow CD}$

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

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

• ${\displaystyle A\rightarrow a}$
• ${\displaystyle A\rightarrow BC}$
• ${\displaystyle AB\rightarrow AC}$

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

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

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

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

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

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

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

Приклад

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

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

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

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

${\displaystyle {\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}}}$

Див. також

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

Примітки

1. наприклад Uwe Schöning. Abschnitt 1.1.2 // Theoretische Informatik – kurz gefasst. — 5. — Spektrum Akademischer Verlag, 2008. — .
2. Klaus W. Wagner. Kapitel 6 // Theoretische Informatik: Eine kompakte Einführung. — Springer, 2003. — .
3. див Rozenberg та Salomaa, Handbook of Formal Languages, S.190
4. Daniel Jurafsky, James H. Martin. Частина 16 // Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. — Prentice Hall, 2009. — .
5. J. C. Martin. Introduction to Languages and the Theory of Computation. — 3. — McGraw-Hill, 2002.

Література

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