Лекція №9 Контекстно-вільні граматики

Звернемо увагу на те, що в правилах НС-грамматики заміняється тільки один символ, ліва ж частина правила не обов'язково складається тільки із цього символу: А→ω. У правилах можуть бути присутнім й іншими символами — контекст: φAψ→ φωψ. Такі правила означають дозвіл заміняти символ А на ω тільки в контексті ? і ?. Сам контекст при цій заміні листується без зміни.

Правила, що використають контекст, назвемо контекстно-зв’язаними, а правила, що не використають контексту, - контекстно-вільними.

НС-грамматики, що містять тільки контекстно-вільні правила виду А→ω, називаються контекстно-вільними (КС-грамматики), або бесконтекстными граматиками.

НС-грамматики, що містять контекстно-зв’язані правила, називаються контекстно- зв’язаними граматиками.

Мови, породжувані КС-грамматиками, називаються КС-языками.

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

КС-грамматики являють собою важливий окремий випадок НС-грамматик. Їхня цінність обумовлена наступними двома обставинами:

по-перше, відмова від контексту, тобто вимога, щоб у лівій частині правила був рівно один символ, робить структуру граматик ще більше простій, що полегшує її вивчення;

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

Загалом така заміна робиться так: нехай є клас елементів X; у сусідстві з елементами деякого класу Y елементи X поводяться інакше, чим у сусідстві з елементами класу Z, так що мають місце правила

YХ→YАВ;

ZX → ZCD

(правила використають контекст).

Уведемо два нових символи — Х₁ і Х₂. Елемент X у позиції після Y позначимо через Х₁, а в позиції після Z — через Х₂.

Тоді приходимо до правил, що не використають контексту

Х₁→АВ;

Х₂ →СD.

Не треба, однак, думати, що всяка контекстно- зв’язана НС-грамматика може бути замінена еквівалентною їй КС-грамматикою. Відомо, що існують НС-мови, що не є КС-мовами, наприклад, мова, що складається із усіляких ланцюжків виду а^пb^па^п(аbа, ааbbаа,... ) або з ланцюжків виду а^пв^пс^п. Від контексту не можна відмовитися, якщо правило повинне забезпечувати перестановку символів, тому що перестановка по своїй істоті є багатомірною операцією. Отже, КС-грамматика не може породжувати мову, що містить ланцюжки, які не можуть бути побудовані без застосування перестановок.

Майже всі наявні приклади НС-мов, що не є КС-мовами, носять абстрактний характер і не мають інтерпретацій у природних мовах.

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

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

Почнемо із числа символів у правій частині. Залежно від числа символів у правій частині правил КС-грамматики можна розділити на бінарні й небінарні.

С-граматики будемо називати бінарними, якщо права частина будь-якого правила містить не більше двох символів.

Наприклад, правила виду А→ВР,

або А→ bВ, А→В,

де А, В, З V_H , b V_т.

КС-грамматики будемо називати небінарними, якщо права частина будь-якого правила містить більше двох символів. Наприклад, граматика із правилами виду А→Ааb, В→АВС, А→ω, де А, В, С V_H, а, b V_T, ω не порожній ланцюжок у цій граматиці, що містить більше двох символів.

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

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

Лінійні граматики — такі КС-грамматики, праві частини правил яких містять не більш ніж по одному входженню нетермінального символу. Таким чином, для бінарних КС-грамматик це правила виду

А→аВ,

де В, А V_Н, а V_т,

для небінарних КС-грамматик правила виду

А→аВаb, А → асВ;

А, В V_H, а, b, з V_T.

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

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

Прикладом металінійної граматики може служити наступна граматика G = ({а,b,с}, {S, Т), {S→ТТ, Т→аТа, T→bТb, T→c}, S).

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

Накладаючи обмеження на склад символів правої частини правил КС-грамматик, Флойд виділив наступні підкласи небінарних, нелінійних граматик.

Операційні граматики — праві частини правил які не можуть містити двох поруч вартих нетермінальних символів. Прикладами правил такого виду можуть служити

А→ВbС;

А→ВаbС,

де А, В, З V_н, а, b V_т.

Граматики предшествий — праві частини правил які можуть містити два поруч стоячих термінальних символи. При цьому є можливість указати, який із цих термінальних символів виникає в словотворі першим, що має більший пріоритет.

Прикладами правил такої граматики можуть служити наступні:

А→ВааВ,

де А, В V_H, а V_T. Є й інші підкласи.

Підкласом лінійних КС-грамматик є однобічні лінійні граматики.

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

Однобічні лінійні граматики підрозділяються на лівосторонні— із правилами виду А→ х. В й А→ х. правобічні— із правилами виду А→У х. А→х. В обох випадках А, В — нетермінальні символи, а х — непустий ланцюжок термінальних символів.

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

З даних визначень ясно, що кожен наступний клас граматик утримується в попередньому.

Взаємозв'язок розглянутих класів граматик можна представити у вигляді графа, зображеного на мал. 13. Таким чином, Кс-грамматики являють собою найбільш важливий підклас НС-грамматик. Це порозумівається наступними чотирма основними причинами:

1. КС-грамматики є основою визначення майже всых вживаних мов програмування.

2. Всі дії системи синтаксичного аналізу для природних мов засновані на КС-грамматиках.

3. Це єдиний тип граматики, теорія якої вивчена й практично перевірена.

4. Всі трансформаційні граматики побудовані на КС-грамматиках.

Всі розглянуті типи граматик породжують чотири типи мов: НС-язык, КС-язык; лінійна мова, А-мова, не вважаючи мови, породжуваного самим загальним типом граматики з необмеженими правилами висновку граматикою типу 0.

Взаємозв'язок між мовами, породжуваними розглянутими типами граматик, буде наступною:

L(O) L(НС)=L(КС) L(Л) L(А).

Вправи:

1. Нехай V_T = {а, b}, побудувати граматики, що породжують наступні мови:

а) мова L= {а^пb^па^п|п≥ 1};

б) мова L= {аⁿ²|n≥ 1};

в) мова L={а^пbⁿ²|п≥ 1).

2. Граматики G₁ й G₂ задані правилами:

Р₁={А→аАbВ, А→bВ, А→А, А→b, В→bAbb, В→В, В→bАb, В→аb};

Р₂ = Р₁-{А→А, В→В}.

Показати, що L(G₁) = L(G₂).

3. Дано граматику G(V_T, V_H, P, S), де V_т = {a, b, c} V_H = {S, В, З}, Р = {S→аSВС, S→аВС, СВ→ВР, аВ→аb, bВ→bb, bС→bс, сВ→сс}. Визначити тип граматики й мову, породжувану нею.

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

5. Задано дві граматики — G₁й G₂ із правилами виду:

P₁ = {S→аb, S→сА, А→bаА, А→а};

Р₂={S→АВ, А→аАb, В→аВb, А→с, В→с}.

Визначити тип граматик.

6. Довести, що мова L — {а^тb^та^пb^п} не є лінійним.

7. Побудувати приклад КС-языка, що не є A-мовою й породжуваного КС-грамматикою, кожне правило якої є або ліволінійним, або праволінійним.

8. Нехай G = (V_т, V_н, Р, S); V_T = {а, b, з}; Р = {S→АВ, А→аАb, В→аВb, А→с, В→с}. Показати, що КС-мова є металінійною, але не лінійною.

9. Граматика G задана правилами Р = {S→аSа, S→bSb, S→ааSаа, S→с}. Показати, що вона не є істотно неоднозначною.

10. Мова L= {а^пb^тс^r|п + т≥r} є КС-мовою. Виписати КС-грамматику, що породжує ця мова. Визначити, до якому більше вузькому класуу мов він належить.