Розділ VIІІ. Граматики та автомати

У цьому розділі розглянуто головні поняття теорії формальних мов і теорії фор­мальних граматик, показано зв'язок між граматиками й автоматами.

Формальні мови та граматики мають велике значення в побудові й реалізації мов програмування. Скінченні автомати та тісно пов'язані з ними конструкції, як, наприклад, регулярні граматики та регулярні вирази, належать до найважли­віших понять інформатики. Різні варіанти скінченних автоматів використову­ють для опису й аналізу технічних пристроїв, різних систем і процесів, програм і алгоритмів. На базі теорії скінченних автоматів сформовано багато складних концепцій теоретичної інформатики. Ця теорія має чимало застосувань у тех­нічній інформатиці та становить важливу частину теоретичної інформатики.

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

Тема 37. Граматики

37.1. Мови

В цьому розділі ми будемо використовувати терміни, схожі за змістом з теорією кодування. Серед них: алфавіт, буква, слово, конкатенація. Але деякі з них мають власні звучання в теорії граматик. Так, слово тут називається ланцюжок.

Нагадаємо, що множину слів або ланцюжків називають мовою. Правила, що задають множину ланцюжків (слів, речень), утворюють синтаксис мови, а опис множини змістів і відповідність між реченнями та змістами – її семантику. Семантика мови залежить від характеру описуваних нею об'єктів, засоби її вивчення для різних типів мов різні. Семан­тика мови математики – формальні теорії. Дослідження семантики мов програ­мування стало окремою частиною теоретичного програмування. Спроби точно описувати семантику природних мов стосуються передусім машинного перекла­ду. Що ж до синтаксису, то його особливості значно менше залежать від призна­чення мови. Можна сформулювати поняття й методи дослідження синтаксису, які не залежать від змісту та призначення мов. Тому найбільших успіхів матема­тична лінгвістика досягла у вивченні синтаксису, де із середини XX ст. розви­нувся спеціальний математичний апарат – теорія формальних породжувальних граматик. Вона дуже важлива як така й ефективна в застосуваннях (мовах програ­мування, штучному інтелекті, машинному перекладі).

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

Розглянемо речення «молодий нападник забив гол». Проаналізуємо його синтаксис. Розглянемо діаграму на рис. 37.1. Вона означає, що речення можна побудувати за допомогою злиття групи підмета й групи присудка, хоча це потребує формального означення. Група підмета складається з означення та підмета, а група присудка – із присудка та додатка. Остаточно отримуємо означення «молодий», підмет нападник, присудок «забив», додаток «гол».

---

Перш ніж увести термінологію та позначення, потрібні для уточнення загаль­них понять у конкретній ситуації, яка зображена на рис. 37.1, зазначимо основні задачі теорії мов.

Нагадаємо, що для заданого алфавіту V мова L — довільна підмножина множи­ни V*, проте довільні підмножини становлять незначний інтерес. Ми хочемо зо­середити увагу на спеціальних мовах, що містять ланцюжки, які завдяки зов­нішній інформації про їх семантику можна вважати осмисленими чи добре сконструйованими.

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

1. Як за заданою граматикою G (і пов'язаною з нею мовою L) породжувати ре­чення L?

2. Як за заданими мовою LV* та реченням V* з'ясувати, чи L?

Щоб перевірити, чи належить якийсь ланцюжок (речення) мові L, потрібно знати, як граматика G породжує L. Далі опишемо загальні принципи породжувальних граматик.

Рис. 37.1.

37.2. Формальні породжувальні граматики

У лінгвістиці природних мов терміни „речення" та „слово" мають різний зміст; тому в математичній лінгвістиці послідовність символів зазвичай називають нейтральним терміном „ланцюжок", а мову, яку розуміють як множину фор­мальних ланцюжків,  формальною.

Означення 37.1. Формальна породжувальна граматика G (далі  граматика G)  це формальна система, задана четвіркою об'єктів G = (V, T, S, P), де V  скінченна непорожня множина, яку називають алфавітом (або словником); T  її підмножина, еле­менти якої називають термінальними (основними) символами; S  початковий символ (SV), P  скінченна множина продукцій (або правил перетворення) вигляду , де  та   ланцюжки над алфавітом V. Множину V\T позначають N, її елементи називають нетермінальними (допоміжними) символами.

Формальні породжувальні граматики часто називають граматиками з фразовою структурою, граматиками безпосередніх складових. Термінальні симво­ли часто називають терміналами, а нетермінальні  нетерміналами.

У теорії формальних граматик усталилися традиції позначень, яких ми будемо дотримуватись. Символи термінального алфавіту позначають малими латинсь­кими буквами чи цифрами, символи нетермінального алфавіту  великими ла­тинськими буквами, ланцюжки над алфавітом V  грецькими буквами. Довжину ланцюжка  позначають l() або ||. Нагадаємо, що множину всіх ланцюжків у алфавіті V позначають V*.

Нас цікавитимуть ланцюжки, які можуть бути породжені продукціями граматики.

Означення 37.2. Нехай G = (V, T, S, P) – граматика, і нехай ₀ = ,  (тобто ₀ – конкатенація ланцюжків ,  та ), ₁ =  – ланцюжки над V. Якщо  – продукція граматики G, то говорять, що ₁ безпосередньо виводиться з ₀, і записують ₀  ₁.

---

Означення 37.3. Якщо ₀, ₁,…, _n – ланцюжки над алфавітом V такі, що ₀  ₁  ₂  …  _n-1  _n, то говорять, що _n виводиться з ₀, і використовують запис . Послідовність кроків для отримання _n з ₀ називають виведенням.

Речення української мови з попереднього прикладу можна вивести в граматиці G, де

V = {речення, група підмета, група присудка, означення, підмет, присудок, додаток, молодий, нападник, забив, гол},

T = {молодий, нападник, забив, гол},

S = речення,

P = {речення  група підмета група присудка,

група підмета  означення підмет,

група присудка  присудок додаток,

означення  молодий,

підмет  нападник,

присудок  забив,

додаток  гол}.

Ця схема породжує тільки одне речення, тому її можна замінити на

L = {молодий нападник забив гол}.

Якщо ми захочемо розширити мову, щоб увести до неї речення з означеннями «талановитий», «надійний», присудком «віддав», і додатками «пас», «м’яч» (тоді мова L матиме вісімнадцять речень), то це можна зробити відповідним розширенням алфавіту та додаванням лише п’яти продукцій до множини P.

Означення 37.4. Мовою, породжуваною граматикою G = (V, T, S, P), називають множину всіх лан­цюжків терміналів, які виводяться з початкового символу S. Її позначають L(G). Отже,

де Т — множина всіх ланцюжків терміналів, включаючи порожній ланцюжок.

Нехай G – граматика з алфавітом V = {S, A, a, b}, множиною терміналів T = {a, b}, початковим символом S і множиною продукцій P = {S  aA, S  b, A  aa}. Знайдемо мову L(G), породжувану цією граматикою.

Із початкового символу S можна вивести ланцюжок aA за допомогою продукції S  aA чи застосувати продукцію S  b, щоб вивести b. З aA, скориставшись продукцією A  aa, можна вивести ланцюжок aaa. Ніяких інших ланцюжків вивести неможливо. Отже, L(G) = {b, aaa}.

Нехай G  граматика з алфавітом V = {S, 0, 1}, множиною терміналів T = {0, 1}, початковим символом S і множиною продукцій P = {S  11S, S  0}. Знайдемо L(G).

Із початкового символу S одержимо 0 (за допомогою другої продукції) чи 11S (за допомогою першої). З 11S можна отримати 110 або 1111S, з 1111S виводиться 11110 або 111111S. Отже, після кожного виведення ми додаємо дві одиниці в кінець ланцюжка чи закінчуємо ланцюжок нулем, тобто L(G) = {0, 110, 11110, 1111110, …}  це множина всіх ланцюжків із парною кількістю тільки 1, після яких (у кінці) обов'язково є один 0.

Ми отримали нескінченну мову L(G), яка складається з нескінченної кількості ланцюжків. Щоб граматика G породжувала нескінченну мову, у мно­жині продукцій має бути принаймні одне рекурсивне правило (наприклад, S  11S).

Дуже важлива проблема побудови граматики для заданої мови.

Наприклад, знайдемо граматику, яка породжує мову {0^m1^m | m = 0, 1, 2,...}. Потрібні дві продукції, щоб побудувати ланцюжок із якоїсь кількості 0, після яких є така сама кіль­кість 1. Перша продукція збільшує ланцюжок зсередини, додаючи зліва 0, а справа  1. Друга продукція замінює початковий символ S на порожній ланцюжок . Одержимо гра­матику G = {V, T, S, P}, де V = {0, 1, S}, T= {0, 1}, S  початковий символ, Р = {S  0S1, S  }.

---

Знайдемо породжувальну граматику для мови {0^m1ⁿ | m, n = 0, 1, 2,...}. Наведемо дві такі граматики:

G₁: V = {S, 0, 1}, T = {0, 1}, P = {S  0S, S  S1, S  };

G₂: V = {S, A, 0, 1}, T = {0, 1}, P = {S  0S, S  1A, S  1, A  1A, A  1, S  }.

Означення 37.5. Граматики G₁ та G₂ називають еквівалентними, якщо L(G₁) = L(G₂).

---

37.3. Типи граматик (ієрархія Хомскі)

Продукція граматики дає змогу заміняти одну послідовність символів іншою. Граматики класифікують за типами продукцій. Розглянемо класифікацію, яку запропонував американський математик і лінгвіст Н. Хомскі (табл. 37.1).

Тип граматики	Обмеження на продукції 
0	немає обмежень
1	||  || чи  = 
2	 = A, де A – нетермінальний символ
3	 = A, причому  = aB чи  = a, де A, B – нетермінальні символи, a – термінальний символ, або S  

Табл. 37.1.

Принцип цієї класифікації полягає в тому, що на продукції накладено певні об­меження. Із цих означень випливає, що кожна граматика типу n, де n = 1, 2, 3, являє со­бою граматику типу n – 1. Граматики типу 2 називають контекстно вільними, бо нетермінал А в лівій частині продукції A можна замінити ланцюжком  в довільному оточенні щоразу, коли він зустрічається, тобто незалежно від кон­тексту. Мову, яку породжує граматика типу 2, називають контекстно вільною.

Якщо в множині продукцій P є продукція вигляду  (але не ), ||  ||, то граматику називають граматикою типу 1, або контекстно залежною, оскільки  можна замінити на  лише в оточенні ланцюжків …, тобто у відпо­відному контексті. Мову, яку породжує граматика типу 1, називають контекстно залежною.

Граматику типу 3 називають регулярною. У ній можуть бути лише продукції AaB, Aa, S, де A, B – нетермінальні символи, a – термінальний символ. Мову, яку породжує граматика типу 3, називають регулярною.

На рис. 37.2 наве­дено діаграму, яка показує співвідношення між граматиками різних типів.

Рис. 37.2.

Мова {0^m1ⁿ | m, n = 0, 1, 2,...} регулярна, бо її породжує регулярна граматика G₂. Мова {0^m1^m | m = 0, 1, 2,...} контекстно вільна, оскільки вона породжена граматикою з продукція ми S  0S1 та S  .

Приклад контекстно вільної мови  мова булевих формул зі змінними a, b, c, яку породжує контекстно вільна граматика G = (V, T, S, P), де V = {S, a, b, c, , , , (, )}, T = {a, b, c, , , , (, )}, а множина продукцій P = { S  (SS), S  (SS), S  S, S  a, S  b, S  c}.

37.4. Дерева виведення

У мовах, породжених контекстно вільними граматиками, виведення можна зобра­жати графічно за допомогою орієнтованих кореневих дерев. Їх називають дере­вами виведення, або деревами синтаксичною розбору. Кореню цього дерева відповідає початковий символ, внутрішнім вершинам  нетермінальні символи, що зустрічаються у виведенні, листкам  термінальні символи. Нехай   лан­цюжок і A    продукція, використана у виведенні. Тоді вершина, що відпо­відає нетермінальному символу A, має синами вершини, які відповідають кож­ному символу ланцюжка  в порядку зліва направо.

Наприклад, визначимо, чи ланцюжок cbab належить мові, породженій граматикою G = (V, T, S, P), де V = {a, b, c, A, B, C, S}, T = {a, b, c}, S  початковий символ, а множина продукцій P = { S  AB, A  Ca, B  Ba, B  Cb, B  b, C  cb, C  b}.

---

Смотрите также файлы

• 38_Skinchenni_avtomati.doc

• dinamika.docx

• dinamika_1.docx

• komivoyazhera.docx

• Lektsiya8.doc