Тема 6. Основні поняття теорії формальних граматик. Операції над формальними мовами

6.1 Мета занять

Засвоїти основні поняття теорії формальних граматик та мов. Набути практичні навичкі здійснення операцій над формальними мовами (ФМ).

6.2 Методичні вказівки з організації самостійної роботи студентів

При опрацюванні теоретичного матеріалу звернять увагу на те, що теорія формальних граматик та мов є основним розділом математичної лінгвістики – специфічної математичної дисципліни, орієнтованої на вивчення структури природних та штучних мов. Ця теорія виникла в 50-х роках у працях американського лінгвіста Ноама Хемського, який виходив виключно з потреб лінгвістики, що традиційно розуміється як наука про побудову природної мови. Однак, незабаром стало зрозуміло, що методи його теорії можуть бути застосовані й до штучних спеціалізованих мов, в тому числі, до алгоритмічних. По характеру математичного апарату, що застосовується, теорія формальних граматик та мов близька до теорії автоматів.

Під граматикою розуміють деяку систему правил, що задає множину ланцюжків символів мови. Ці ланцюжки можуть інтерпретуватись як мовні об’єкти різних рівнів: як словоформи, словосполучення чи речення. Словоформа (чи просто слово) – (послідовність) ланцюг морфем. Морфема – найменша граматично значима частина слова (словоформи). Наприклад: словоформа “ведший” складається з морфем “вед”+“ш”+“ий” (корінь+суфікс+закінчення), де “+” – границя морфем. Словосполучення та речення - ланцюг словоформ =>

Граматика мови – це скінченна множина правил, що рекурсивно задають мову як синтаксичну структуру. Граматику можна розглядати як теорію структури цієї мови, тобто теорию закономірностей побудови речень, що повторюються. Ці закономірності називаються синтаксичною структурою мови. Синтаксис мови – правила побудови речень в мові чи правила побудови конструкцій мови. Семантика мови – тлумачення цих правил, правила використання синтаксису.

Перша основна вимога до граматики, що формалізується, - щоб вона приписувала кожному реченню мови його структурний опис. Це правило визначає, з яких елементів побудоване речення, який їх порядок, розташування. Структурний опис буде тоді і тільки тоді однозначним, коли в мові через граматику однозначно визначені його синтаксичні одиниці та ієрархічний взаємозв’язок між ними.

Друга вимога до граматки мови – вона повинна бути скінченною, тобто, якщо допустити граматики з невизначеною множиною правил, то сама проблема побудови граматик знімається.

Формальні граматики мають справу з абстракціями, що виникають при узагальненні понять словоформа, словосполучення, речення. Якщо звичайні граматики дозволяють задавати множини правил побудови речень, то формальні граматики - це деякий спосіб вивчати й описувати множини правил.

Між звичайними і формальними граматиками є істотна різниця. У формальних граматиках всі твердження формулюються в термінах невеликого числа чітко визначених і досить елементарних символів та операцій. Це робить формальні граматики порівняно простими з погляду їхньої логічної будови та полегшує вивчення їхніх властивостей. Однак формальні граматики виявляються досить громіздкими для опису природної мови і тому призначаються тільки для наукового, теоретичного дослідження найбільш загальних властивостей мови.

Розрізняють:

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

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

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

Клас породжуючих граматик

Породжуючою граматикою називається впорядкована система (четвірка)

,

де – кінцева непуста множина символів, яку називають термінальним (основним) словником G.

Термінальний словник – набір вихідних елементів, з яких будуються ланцюжки, що породжуються граматикою, або словник основних слів мови, з яких будуються речення.

– кінцева непуста множина символів, яку називають нетермінальним (допоміжним) словником.

Нетермінальний словник - набір символів, якими позначаються класи або ланцюжки вихідних елементів, або словник синтаксичних типів.

Елементи та називають відповідно термінальними або нетермінальними символами.

– кінцева множина символів, називається словником граматики G.

Довільна, кінцева послідовність ω елементів V називається ланцюжком у словнику V.

Порожній ланцюжок позначається e.

.

.

Довжина ланцюжка позначається |ω|.

Ланцюжок символів словника V отримується за допомогою операції з'єднання (зчеплення, конкатенації) ∩.

Наприклад, .

Операція конкатенації асоціативна, але не комутативна!

S – початковий символ (символ нетермінального алфавіту, називається аксіомою граматики).

S – виділений нетермінальний символ, що позначає клас всіх тих мовних об'єктів, для опису яких призначається дана граматика.

S називається аксіомою, або метою граматики. .

Р – синтаксичні правила граматики або кінцева множина ланцюжків виду:

де φ, ψ – слова в словнику V, і ланцюжок φ містить принаймні один символ зі словника .

Кінцеве двомісне відношення → інтерпретується як “замінити φ на ψ ”, або “поставити ψ замість φ ”. Це відношення має властивості асиметричності та иррефлексивності (рефлексивності?).

· Відношення R рефлексивне, якщо aRa

· Відношення R антирефлексивне, якщо ні для якого а не виконується aRa.

· Відношення R симетричне, якщо .

Антисиметричне відношення: якщо aRb і .

Ланцюжки називають правилами підстановки або просто правилами граматики, множина Р – схема граматики.

Якщо задано граматику , то говорять, що:

1. Ланцюжок отримується безпосередньо з ланцюжка ω застосуванням правила , якщо , і .

2. Послідовність ланцюжків є φ – вивід ланцюжка ψ, якщо для кожного i виходить з , .

Наявність φ – виводу ланцюжка ψ позначається

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

3. Ланцюжок ψ може бути виведений з φ, якщо він отримується із φ застосуванням деяких правил граматики G.

4. Вивід ланцюжка ψ вважається закінченим, якщо не існує ланцюжка, який виходить з ψ.

5. Ланцюжок, що складається тільки з термінальних символів, називається термінальним ланцюжком (кожний термінальний ланцюжок - це ланцюжок у словнику , до якого не застосовується жодне з правил граматики G).

− Множина ланцюжків, що виводяться в граматиці G, називається мовою, породженою цією граматикою, і позначається L(G).

− Мова L(G) називається термінальною, якщо L – множина термінальних ланцюжків граматики G.

Домовимося при написанні конкретних граматик першими рядковими латинськими буквами а, b, с позначати елементи термінального словника ; елементи нетермінального словника – прописними латинськими А, В, С, а елементи загального словника V – рядковими грецькими α, β, γ.

Речення, складені із цих символів, позначають останніми буквами відповідних алфавітів:

x, y, z... – речення, складені з елементів ;

X, Y, Z... – речення, складені з елементів ;

ω, φ, ψ... – речення, складені з елементів V.

позначає, що мається на увазі множина всіх ланцюжків, які можуть бути отримані із символів множини V.

Приклад: Задана граматику

, де

;

;

S = C;

.

Нехай ω = aCb, ω = aaCbb.

Ланцюжок ω безпосередньо виводиться з ω у результаті застосування одного правила:

Φ – віивід: аСb, ааСbb, аааСbbb, ааааbbbb.

Останній ланцюжок є термінальним.

Довжина виводу дорівнює трьом.

З прикладу видно, що породжуюча граматика не є алгоритмом.

Правила підстановки граматики - це не послідовність предписаний, а сукупність вирішень.

Це означає:

1) Правило розуміється в граматиці як “ φ замінити на ψ ” (але можна й не замінювати), тоді як в алгоритмі воно означало б “ φ варто замінити на ψ ” (не можна не замінити).

2) Порядок застосування правил у граматиці довільний, тоді як в алгоритмі був би заданий твердий порядок застосування окремих інструкцій.

− Дві граматики називають слабко еквівалентними, якщо вони породжують одну й ту ж мову, ; або дві граматики називаються слабко еквівалентними, якщо співпадає множина породжуваних ними фраз.

− Дві граматики називають сильно еквівалентними, якщо вони не тільки породжують ті самі ланцюжки, але й приписують однаковим ланцюжкам однакові описи структури.

Інакше кажучи, під сильною еквівалентністю розуміється співпадання множини фраз разом зі способами їхнього опису.

Основний суб'єкт застосування теорії граматик - не довільні граматики, а граматики деяких спеціальних типів, найбільш важливих як у теоретичному, так і в практичному аспекті.

Виділення цих типів виконується по виду правил.

У теорії Хомського виділяються та вивчаються 4 типи мов, що породжуються відповідно чотирма типами граматик.

Ці граматики виділяються шляхом накладення на систему правил P обмежень, що послідовно підсилюються.

Граматика називається граматикою типу 0 у тих випадках, коли не накладається ніяких обмежень на правила , де φ і ψ можуть бути будь-якими ланцюжками зі словника V.

Граматика називається граматикою типу 1, якщо в системі 1 правила задовольняють умові ,

У БС (безпосередньо складових)-граматиці (рос. – НС-грамматика) на кожному кроці виводу дозволяється замінювати тільки один символ.

де А - нетермінальний символ, φ,ψ,ω - ланцюжки зі словника V.

Вочевидь БС-граматика є нескорочуваною граматикою

Таким чином у граматиках типу 1 окремий нетермінальний символ А переходить у непустий ланцюжок ω в контексті φ1 і φ2 (φ1 та φ2 можуть бути порожніми ланцюжками). Граматики типу 1 називаються контекстними граматиками; граматиками безпосередньо складових; (БС-граматики); контексно зв'язані граматики.

Граматика називається граматикою типу 2 – безконтекстною, якщо в системі правил Р припустимі лише правила виду , де А - нетермінальний символ, ω - непустий ланцюжок з V.

Відповідно до правил цієї граматики, заміна А на ω відбувається незалежно від контексту.