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

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

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

Визначення[ред.ред. код]

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

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

Властивості[ред.ред. код]

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

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

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

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

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

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

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

Нормальні форми[ред.ред. код]

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

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

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

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

Альтернативне позначення[ред.ред. код]

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

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

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

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

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

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

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

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

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

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

  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.