Контекстно-залежна граматика (скорочено КЗ-граматика) — формальна граматика типу 1 в ієрархії Чомскі. Особливість КЗ граматик в тому, що правила виводу здійснюють заміну нетермільнального символу лише у визначеному контексті.
Визначення Контекстно-залежна граматика, це формальна граматика де — множина нетермінальних символів — множина термінальних символів — початковий символ — правила виводу виду або , за умов:
відсутнє в правій частині правил виводу
Властивості
За єдиним винятком, визначені правила виводу мають вид та .
Це означає, що нетермінальний символ в контексті та буде замінено на . Але, в той час, як довжина має бути не менше за одиницю, і і можуть бути порожніми.
Наступні приклади крайніх випадків відповідають визначенню:
Аби зробити можливим роботу з порожнім словом, дозволяють правило , за умови відсутності в правій частині правил виводу.
Контекстно-залежні та монотонні граматики
Правила виводу КЗ-граматики не скорочують рядок в лівій частині. За винятком правила для правил виконується нерівність . Таким чином, КЗ-граматика завжди монотонна. КЗ- та монотонні граматики породжують однаковий клас мов.
Деякі автори наводять визначення КЗ-граматик в контексті монотонних.наприклад Правила виводу виду розглядають як типову або канонічну форму правил КЗ-граматик.
Нормальні форми
Кожній КЗ-граматиці відповідає граматика в нормальній формі Куроди з правилами виводу виду:
Граматика в нормальній формі Куроди монотонна, але не завжди контекстно-залежна.
КЗ нормальна форма подовжуюча, якщо має правила виду:
Кожній КЗ граматиці відповідає подовжувальна граматика в нормальній формі.див Rozenberg та Salomaa, Handbook of Formal Languages, S.190
Альтернативне позначення
Мовознавці використовують інші позначення для правил виводу.. Правила підставляння визначають аналогічно правилам виводу, а в правій частині вказують контекст, в якому можна застосувати правило:
Мови породжені КЗ-граматиками
Контекстно-залежні граматики породжують контекстно-залежні мови. Тобто, кожна КЗ граматика породжує КЗ мову, і для кожної КЗ мови існує КЗ граматика, що її породжує.
Контекстно-залежні мови можна розпізнати недетермінованою лінійно-обмеженою машиною Тюринга (недетермінована машина Тюринга зі стрічкою обмеженої довжини).
Визначення приналежності слова мові () для КЗ-мов розв'язувана.
Приклад
Контекстно-залежну мову слів, які складаються з однакової кількості літер a за якими йдуть b та c, визначають наступною КЗ граматикою:
з термінальними символами та нетермінальними та правилами виводу
Слово можна отримати таким чином (підкреслено контекст, в якому відбувається заміна):
Див. також Граматика залежностей
Примітки
Література