НОУ ІНТУІТ, Лекція, Контекстно-вільні граматики

15.1. Загальний алгоритм аналізу

Щоб визначити те, що називають контекстно-вільною граматикою (КС-граматикою), треба:

• вказати кінцеве безліч, зване алфавітом; його елементи називають символами; кінцеві послідовності символів називають словами (у цьому алфавіті );
• розділити всі символи алфавіту на дві групи: термінальні ("остаточні") та нетермінальні ("проміжні");
• вибрати серед нетермінальних символів один, званий початковим;
• вказати кінцеве число правил граматики , кожне з яких має мати вигляд , де - деякий нетермінальний символ, а - слово (до нього можуть входити і термінальні, і нетермінальні символи).

Нехай фіксована КС-граматика (ми часто опускатимемо префікс "КС-", оскільки інших граматик у нас не буде). Висновок у цій граматиці називається послідовність слів , у якій складається з одного символу, і цей символ - початковий, а виходить із заміною деякого нетермінального символу на слово за одним із правил граматики . Слово , складене з термінальних символів, називається виведеним , якщо є висновок , який закінчується. Безліч всіх слів, що виводяться (з термінальних символів) називається мовою, що породжується даною граматикою.

У цій та наступній лекції нас буде цікавити таке питання: дана КС-граматика; побудувати алгоритм , який за будь-яким словом перевіряє, чи виводиться воно в цій граматиці .

Приклад 1. Алфавіт:

Приклади слів, що виводяться:

Приклад 2. Інша граматика, що породжує ту ж мову:

Алфавіт : ( ) [ ] T E

Для кожного нетермінального символу можна розглянути безліч усіх термінальних слівсимволів , які з нього виводяться (аналогічно тому, як це зроблено для початкового символу у визначенні виведення граматики ). Кожне правило граматики можна як властивість цих множин. Покажемо це на прикладі щойно наведеної граматики. Нехай і - безліч слів (з дужок), що виводяться з нетерміналів T і E відповідно. Тоді правилам граматики відповідають такі властивості:

E	E містить порожнє слово
E-> TE	якщо слово A належить T , а слово B належить E , то слово AB належить E
T->[E]	якщо A належить E , то слово [A] належить T
T->(E)	якщо A належить E , то слово (A) належить T

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

15.1.1. Сформулювати точно та довести це твердження для довільної контекстно-вільної граматики.

15.1.2. Побудувати граматику, в якій виводяться слова

(а) 00..0011..11 (число нулів дорівнює числу одиниць);

(б) 00..0011..11 (число нулів удвічі більше від кількості одиниць);

(в) 00..0011..11 (число нулів більше за кількість одиниць);

15.1.3. Довести, що немає КС- граматики , у якій було б виведені слова виду 00..0011..1122..22 , у яких числа нулів, одиниць і двійок рівні, і вони.

Вказівка. Довести наступну лему про довільну КС-граматику: для будь-якого досить довгого слова, що виводиться в цій граматиці, існуєтаке його уявлення у вигляді , що будь-яке слово виду , де й повторені однакове число разів, також виводиться у цій граматиці . (Це можна встановити, знайшовши нетермінальний символ, що виявляється своїм власним "спадкоємцем" у процесі виведення.)

Нетермінальний символ можна розглядати як "родове ім'я" для слів, що виводяться з нього. У наступному прикладі для наочності як нетермінальні символи використано фрагменти українських слів, укладені у кутові дужки. (З погляду граматики кожен такий фрагмент – один символ!)

---