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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Контекстно-залежна граматика (скорочено КЗ-граматика) — формальна граматика типу 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|. Таким чином, КЗ-граматика завжди монотонна. КЗ- та монотонні граматики породжують однаковий клас мов.

Деякі автори наводять визначення КЗ-граматик в контексті монотонних.[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^nb^nc^n|n\geq 1\} слів, які складаються з однакової кількості літер a за якими йдуть b та c, визначають наступною КЗ граматикою[5]:

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}

Посилання[ред.ред. код]

  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.

Література[ред.ред. код]

  • 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