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

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

Формальна породжувальна граматика G(у подальшому грама­тика G)- це формальна система, визначена четвіркою об'єктів G=(V, T, S, P), де V— скінченна непорожня множина, яку називають алфавітом (або словником); T -її підмножина, елементи множини Т називають термінальними (основними) символами; S— початковий символ(S∈ V), Р - скінченна множина продукцій (або правил перетворення) вигляду ξ → η, де ξ таη — ланцюжки в алфавіті V.

МножинуV\TпозначаютьN, її елементи називають нетермінальними (допоміжними) символами.

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

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

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

Нехай G=(V, T, S, P)- граматика, і нехай α ₀=σ ξ τ, ξ ≠ λ (тобто α ₀ – конкатенаціяσ, ξ таτ) та α ₁=σ η τ - ланцюжки над V. Якщо ξ → η є продукцією граматики G, то кажуть, що α ₁ безпосередньо виво­диться зα ₀, і записуютьα ₀⇒ α ₁.

Якщо α ₀, α ₁, …, α _n - ланцюжки над V такі, що

α ₀⇒ α ₁⇒ α ₂, …, ⇒ α _{n -1}⇒ α _n,

то кажуть, щоα ₀ породжуєα _n, та використовують записα ₁⇒ α _n.

Послідовність кроків для отриманняα _п з α ₀ називають виведенням.

Приклад 9.2. Речення українською мовою, наведене у прикладі 9.1, може бути виведене у граматиці G=(V, T, S, P), де

V = { , , , , , , , маленька, дівчина, нагодувала, котика},

Т= {маленька, дівчина, нагодувала, котика},

початковий символ , а множина Р містить такі продукції:

→ ,

→ , ,

→ , ,

→ маленька,

→ дівчина,

→ нагодувала,

→ котика.

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

L = {маленька дівчина нагодувала котика}.

Та якщо ми в цьому випадку захочемо розширити мову, щоб увести до неї речення з означеннями " сусідська", " весела", присудком " попестила", і додатками " цуцика", " кролика" (тоді L матиме 18 речень), то це можна зробити відповідним розширенням алфавіту та додаванням лише п'яти продукцій до множини Р.▲

Приклад 9.3. Розглянемо граматикуG=(V, T, S, P). Нехай V ={ a, b, A, B, S }Т={а, b}, S - початковий символ, Р={S→ АВа, А→ ВВ, В→ аb, АВ→ b}. ЛанцюжокАаbа безпосередньо виводиться зАВа у цій граматиці, оскільки В-аb є продукцією граматики. Ланцюжок аbаbаbа породжується ланцюжкомАВа, оскільки

АВа⇒ Ааbа⇒ ВВаbа⇒ Ваbаbа⇒ аbаbаbа

за допомогою послідовного використання продукцій В→ аb, А→ ВВ, В → аb таВ→ аb.▲

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

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

Приклад 9.4. Нехай G - граматика з алфавітомV={S, А, а, b}, множиною терміналів Т={а, b}, початковим символом S і множи­ною продукцій Р={S→ аА, S → b, А→ аа}. Знайдемо мову L (G), яка породжується цією граматикою.

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

Приклад 9.5. НехайG-граматика з алфавітом S ={ S, 0, 1}, Т={0, 1}, початковим символом S та множиною продукцій Р={ S → 11 S, S→ 0}. Знайдемо L (G).

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

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

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

Приклад 9.6. Знайдемо граматику, яка породжує мову {0 ^m 1 ^m | т=0, 1, 2,...}. Потрібно дві продукції, щоб побудувати ланцюжок, який складається з деякої кількості нулів, за якими є така ж кіль­кість одиниць. Перша продукція нарощує ланцюжок зсередини, додаючи зліва від центру 0, а справа 1. Друга продукція замінює S на порожній ланцюжок λ. Розв'язком є граматика G=(V, T, S, P), V ={0, 1, S }, T = {0, 1}, S - початковий символ, Р ={ S→ 0 S 1, S→ 𝜆 }. ▲

Приклад 9.7. Знайти граматику, яка породжує мову {0 ^m 1 ⁿ |m, n =0, 1, 2,...}.

Таких граматик наведемо дві:

G ₁: V ={ S, 0, 1}, T ={0, 1}, P ={ S → 0 S, S → S 1, S → λ };

G2: V ={ S, A, 0, 1}, T ={0, 1}, P ={ S → 0 S, S → 1 A, A→ 1 A, A→ 1 A, S → λ }

Пропонуємо обґрунтувати, що обидві ці граматики справді породжують мову {0 ^m 1 ⁿ |m, n =0, 1, 2,...} (див задачі 3, 4). Цей приклад свідчить, що дві різні граматики можуть породжувати одну мову. ▲

Граматики G ₁таG₂ називають еквівалентними, якщо L (G ₁)=L(G ₂). Граматики G ₁таG₂з прикладу 9.7 еквівалентні.

Іноді мову, яку легко описати, доводиться задавати достатньо складною граматикою.

Приклад 9.8. Побудуємо граматику, яка породжує мову {0^m1^m2^m|п=0, 1, 2,...}.

Розв'язком цієї задачі є така граматика: G=(V, T, S, P)V={0, 1, 2, S, А, В}, Т={0, 1, 2}, початковий символ S, множина продукцій

.▲

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

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

Приклад 9.6. Знайдемо граматику, яка породжує мову {0 ^m 1 ^m | т=0, 1, 2,...}. Потрібно дві продукції, щоб побудувати ланцюжок, який складається з деякої кількості нулів, за якими є така ж кіль­кість одиниць. Перша продукція нарощує ланцюжок зсередини, додаючи зліва від центру 0, а справа 1. Друга продукція замінює S на порожній ланцюжок λ. Розв'язком є граматика G=(V, T, S, P), V ={0, 1, S }, T = {0, 1}, S - початковий символ, Р ={ S→ 0 S 1, S→ 𝜆 }. ▲

Приклад 9.7. Знайти граматику, яка породжує мову {0 ^m 1 ⁿ |m, n =0, 1, 2,...}.

Таких граматик наведемо дві:

G ₁: V ={ S, 0, 1}, T ={0, 1}, P ={ S → 0 S, S → S 1, S → λ };

G2: V ={ S, A, 0, 1}, T ={0, 1}, P ={ S → 0 S, S → 1 A, A→ 1 A, A→ 1 A, S → λ }

Пропонуємо обґрунтувати, що обидві ці граматики справді породжують мову {0 ^m 1 ⁿ |m, n =0, 1, 2,...} (див задачі 3, 4). Цей приклад свідчить, що дві різні граматики можуть породжувати одну мову. ▲

Граматики G ₁таG₂ називають еквівалентними, якщо L (G ₁)=L(G ₂). Граматики G ₁таG₂з прикладу 9.7 еквівалентні.

Іноді мову, яку легко описати, доводиться задавати достатньо складною граматикою.

Приклад 9.8. Побудуємо граматику, яка породжує мову {0^m1^m2^m|п=0, 1, 2,...}.

Розв'язком цієї задачі є така граматика: G=(V, T, S, P)V={0, 1, 2, S, А, В}, Т={0, 1, 2}, початковий символ S, множина продукцій

.▲

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

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

Таблиця 9.1

Тип граматики	Обмеження на продукціїξ → η
	Немає обмежень
	або η =λ
	ξ = A, де А - нетермінальний символ
	ξ = A, причому η = aB або η = a, де А, B- нетермінальні символи, а – термінальний символ, або

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

Граматику типу 1 називають контекстно залежною. Коли у такій граматиці є продукція γ A δ → γ μ δ (тобто тут ξ =γ A δ, η =γ μ δ), у якій хоча б один з ланцюжків γ, δ відмінний від λ, то нетермінал А може бути замі­нений ланцюжком μ лише в ото­ченніγ та δ, тобто у відповідному контексті, звідси походить назва.

Граматику типу 3 називаєтютьрегулярною. Ця граматика може мати продукції лише у формі А→ аВ, A→ а, S→ 𝜆, де А, В - нетермі­нали, а -термінал.

Співвідношення між граматиками різних типів ілюструє діагра­ма на рис. 9.2.

Відповідно до граматик відбувається й класифікація мов. Мову називають контекстно залежною, якщо існує контекстно залежна граматика, яка породжує цю мову. Мову називають контекстно вільною, якщо існує контекстно вільна граматика, яка породжує цю мову. І, нарешті, мову називають регулярною, якщо існує регу­лярна граматика, яка її породжує.

Приклад 9.9.Мова {0 ^m 1 ⁿ |m, n=0, 1, 2,...} є регулярною, оскільки вона може бути породжена регулярною граматикою G ₂ прикладу 9.7. ▲

Приклад 9.10.Мова {0 ^m 1 ^m | т=0, 1, 2,...} є контекстно вільною, оскільки вона породжена граматикою з продукціями S → 0 S 1 та S→ 𝜆. Проте ця мова не є регулярною: не існує регулярної грама­тики, яка б цю мову породжувала. Цей факт потребує окремого доведення (див. приклад 9.37).▲

Приклад 9.11.Мова {0 ^m 1 ^m 2 ^m |т=0, 1, 2,...} є контекстно залеж­ною, оскільки вона може бути породжена граматикою типу 1 з прик­ладу 9.8. Ця мова не може бути породжена жодною граматикою типу 2, цей факт також потребує окремого доведення (див. приклад 9.38).▲

Приклад 9.12. Мова булевих формул зі зміннимиа, b, спороджена контекстно вільною граматикоюG=(V, T, S, P), деV={ S, а, b, с, ∨, ∧,, (,)}, Т={ а, b, с, ∨, ∧,, (,)}, а множина продукцій

.▲

Приклад 9.13.Якщо в попередній граматиці перші три правила, які вводять операції∨, ∧ та і, замінити чотирма правилами, які вводять операції +, -, * та /, то отримаємо контекстно вільну грама­тику, яка породжує мову арифметичних виразів. Ця мова відріз­няється від звичайної мови арифметичних виразів тим, що не враховує асоціативності додавання і множення, а також пріоритетів операцій, і тому її вирази містять забагато дужок. Аналогічне заува­ження стосується й мови з прикладу 9.12. Ближча до звичайної мова арифметичних виразів зі зміннимиа, b, сзадається складнішою контекстно вільною граматикою. Її алфавіти V ={ S, R, К, М, а, b, с, +, -, *, /, (,)}, Т={а, b, с, +, -, *, /, (,)}, а множина продукцій Р містить такі правила: S→ R, S→ S+R, S→ S-R, R→ M, R→ R*M, R→ R/M, M→ (S), M→ K, K→ a, K→ b, K→ c.

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