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

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

Визначення

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

$N$ — множина нетермінальних символів
$T$ — множина термінальних символів
$S\in N$ — початковий символ
$P$ $P$ — правила виводу виду $\alpha X\beta \rightarrow \alpha \gamma \beta$ $\alpha X\beta \rightarrow \alpha \gamma \beta$ або $S\rightarrow \varepsilon$ $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|$ . Таким чином, КЗ-граматика завжди монотонна. КЗ- та монотонні граматики породжують однаковий клас мов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад

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

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

$S\rightarrow aSBC\mid aBC$
$CB\rightarrow HB$
$HB\rightarrow HC$
$HC\rightarrow BC$
$aB\rightarrow ab$
$bB\rightarrow bb$
$bC\rightarrow bc$
$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}}$

Див. також

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

Примітки

↑ наприклад Uwe Schöning. Abschnitt 1.1.2 // Theoretische Informatik – kurz gefasst. — 5. — Spektrum Akademischer Verlag, 2008. — ISBN 9783827418241.
↑ Klaus W. Wagner. Kapitel 6 // Theoretische Informatik: Eine kompakte Einführung. — Springer, 2003. — ISBN 9783540013136.
↑ див Rozenberg та Salomaa, Handbook of Formal Languages, S.190
↑ Daniel Jurafsky, James H. Martin. Частина 16 // Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. — Prentice Hall, 2009. — ISBN 9780131873216.
↑ 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. — ISBN 9783540604204.
Katrin Erk, Lutz Priese. Theoretische Informatik: Eine umfassende Einführung. — Springer, 2008. — ISBN 9783540763192.

[1] наприклад Uwe Schöning. Abschnitt 1.1.2 // Theoretische Informatik – kurz gefasst. — 5. — Spektrum Akademischer Verlag, 2008. — ISBN 9783827418241.

[2] Klaus W. Wagner. Kapitel 6 // Theoretische Informatik: Eine kompakte Einführung. — Springer, 2003. — ISBN 9783540013136.

[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. — ISBN 9780131873216.

[5] J. C. Martin. Introduction to Languages and the Theory of Computation. — 3. — McGraw-Hill, 2002.

[1]

[2]

[3]

[4]

[5]