Відкрити головне меню

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

Зміст

ВизначенняРедагувати

Контекстно-залежна граматика, це формальна граматика   де

  •   — множина нетермінальних символів
  •   — множина термінальних символів
  •   — початковий символ
  •   — правила виводу виду   або  , за умов:
    •  
    •  
    •  
    •   відсутнє в правій частині правил виводу

ВластивостіРедагувати

За єдиним винятком, визначені правила виводу мають вид   та  .

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

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

  •  
  •  
  •  

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

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

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

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

Нормальні формиРедагувати

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

  •  
  •  
  •  
  •  

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

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

  •  
  •  
  •  

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

Альтернативне позначенняРедагувати

Мовознавці використовують інші позначення для правил виводу.[4]. Правила підставляння визначають аналогічно правилам виводу, а в правій частині вказують контекст, в якому можна застосувати правило:  

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

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

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

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

ПрикладРедагувати

Контекстно-залежну мову   слів, які складаються з однакової кількості літер a за якими йдуть b та c, визначають наступною КЗ граматикою[5]:

  з термінальними символами   та нетермінальними   та правилами виводу  

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  

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

 

ПосиланняРедагувати

  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.