Граматики безпосередньо складових

Неукорочуючі граматики - граматики, у яких для будь-якого правила φ →ψ справедливе співвідношення |φ|≤|ψ|. Правила такого виду також називаються що не укорочують.

Розглянемо приклад граматики, що не укорочує. Нехай задана G = (V_т, V_н, Р, S), де

V_T={а, b}, V_н={S}, Р={F₁, F₂, F₃, F₄}

F₁: S → аа, F₃:S→аSа,

F₂: S →bb, F₄: S → bSb.

Дано слово bSb. У результаті підстановки кожного із чотирьох правил ми одержуємо нове слово, довжина якого не менше довжини вихідного слова: bааb, bbbb, bаSаb, bbSbb.

Граматики безпосередньо складових — граматики із правилами виду: φAψ→φωψ або А→ω, де А—нетермінальний символ; ω - довільний непустий ланцюжок.

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

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

Пояснимо це на прикладі. Допустимо, що в граматиці, що не укорочує, має місце правило виду АВ→ВА, де А и В - нетермінальні символи.

Таке правило може бути замінено чотирма правилами граматики безпосередньо складових:

АВ→1B;

1B→12;

12→В2;

В2→ВА,

де 1, 2 нові нетермінальні символи, які не зустрічаються ні в яких старих правилах. Послідовне застосування цих правил рівносильно застосуванню правила АВ→ВА, причому така заміна не може привести до появи «зайвих» виводів, оскільки символи 1, 2— нові.

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

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

Лівоконтекстною НС-грамматикою будемо називати граматику із правилами виду:

φA→φω,

a правоконтекстною—грамматику із правилами виду:

Aφ →ωφ,

де А — нетермінальний символ,

φ і ω — ланцюжка в алфавіті V = V_T U V_H.

Мова, породжувана лівоконтекстною граматикою G, будемо називати лівоконтекстною мовою L(G); мова, породжувана правоконтекстною граматикою G', — правоконтекстною мовою й позначати L(G').

Щодо цих мов доведені наступні теореми:

Теорема (8). Клас лівоконтекстних мов не збігається із класом контекстно-вільних мов.

Теорема (9). Клас правоконтекстних мов не збігається із класом контекстно-вільних мов.

Граматика безпосередньо-складових називається НС-грамматикою, відзначеної праворуч (НС — ОП-грамматикою), якщо кожне правило має вигляд:

φAψ→φωψ=φω’αψ

де a V.

НС-грамматика називається НС-грамматикою, відзначеною ліворуч (НС — ОЛ-грамматика), якщо кожне її правило має вигляд:

φAψ→ φωψ= φα ω’ψ, a V

Мають місце теореми:

Теорема (10). Для будь-який НС - Оп-грамматики можна побудувати слабко еквівалентну Кс-грамматику.

Теорема (11). Для будь-який НС — ОЛ-грамматики можна побудувати слабко еквівалентну КС_:граматику.

Для вивчення властивостей Нс-грамматик розглянемо маленький фрагмент граматики російської мови, заданого наступними правилами:

F₁: → ;

F₂: →ПС;

F₃ : → Г ;

F₄ : П → маленький, пустотливий, гарний;

F₅: С →м'яч, хлопчик, дівчинка;

Fe: Г → втратив, ударив, кинув.

Правила F₄—F₆ — це в дійсності група правил, оскільки вони вказують кілька можливостей для кожного символу П, С, Г.

У розглянутій граматиці термінальними символами будуть слова, перераховані в правилах: V_т = {маленький, пустотливий, гарний, м'яч, хлопчик, дівчинка, втратив, ударив, кинув}.

Нетермінальними символами будуть синтаксичні категорії

( —група дієслова, —група іменника, Г -дієслово,

С — іменник; П — прикметник, — речення):

V_н= { , , , Г, С,П}.

Початковим символом буде поняття речення. Виведені термінальні ланцюжки - правильні речення даної мови.

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

Кожний С-маркер містить у вигляді міток при скінченних вузлах перелік слів, з яких складене дане речення (мал. 12).

У розглянутому речення складовими є - «м'яч», «гарний м'яч», «упустив гарний м'яч», а «упустив гарний»- не є складовій. Кожна складова зводиться до деякого вузла дерева. Якщо цей вузол, допустимо, позначений З, то говорять, що складова належить до типу С.

Ті складові, з яких конструкція безпосередньо утворена, є безпосередніми складовими.

Наприклад, і — безпосередні складові речення. Є безпосередні складові для С и Г — це відповідно П и С, і Г и і т.д. Очевидно, граматика не може вважатися задовільної, якщо не дає породжуваним реченням структурного опису - хоча б у вигляді розкладання на безпосередні складові.

Таким чином, граматика повинна забезпечувати З-маркером кожне з нескінченного числа речень.

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

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

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

Виділимо три види рекурсивних елементів.

Елемент А називається ліворекурсивним, якщо підлегле йому дерево містить А тільки в самому лівому ланцюзі. (Дерево, підлегле А, — це дерево, що може бути виведене з А.)

Елемент A називається праворекурсивним, якщо підлегле йому дерево містить А тільки в крайньому правому ланцюзі.

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

Граматика (G = (V_т, V_H, S, Р) називається граматикою із самовставлянням, якщо для деякого A V_н існує висновок А = >φAψ, де φ і ψ — не порожні слова в V.

Граматика G називається однозначною, якщо для кожного слова х L_G всі його виводи мають те саме дерево.

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

У прикладах такого роду істотно не «статистичне» остаточне накреслення, а «динаміка» процесу граматичного висновку. Подібного роду неоднозначність відіграє істотну роль для мов програмування. Тому виникає питання про однозначність різних типів граматик і можливості.знайти однозначну граматику певного типу.

Граматика G називається неоднозначної, якщо є ланцюжок х L_G, що може бути виведена двома істотно різними способами. При цьому під істотно різними висновками розуміється наступне:

Граматиці G = (V_т, V_н, S, Р) із правилами виду φ₁→ψ₁, φ₂→ψ₂, …, φ_k→ψ_k поставимо у відповідність граматику G' = (V', V', S', Р', у якої V' = V_H, S' = S, V'_т = V_T, U {(φ₁, (φ₂, … (φ_k)}, т. е. для кожного правила φ_i→ψ_i системи Р к термінальному словнику додається дужка (φ_i(i= 1, 2, ... k).

Система Р' виходить із системи Р заміною кожного правила виду φ_i→ψ_i правилом φ_i→( _φiψ_i)

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

Ланцюжок х' називається структурним описом ланцюжка х.

Приклад. Нехай G = ({0,1}, S, S, Р); Р = {S→0, S→S1S}, тоді G'= ({0,1(S)}, S, S, Р); Р= {S→(_S0), S→(_SS1S)}, ланцюжок 01010 мови L_G може бути виведена - різними способами:

1. S→S1S→01S→01S1S→0101S→01010;.

2. S→S1S→S10→S1S10→01S10→01010.

Їм відповідають різні структурні описи, отримані в L_G':

1. (_S(_S0)1(_S(_S0)1(_S;0)));

2. (_S(_S(_S0) 1(_S0)) 1(_S0)).

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

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

Якщо задано конкретну граматику G одного з типів і потрібно встановити, чи є вона неоднозначної, то алгоритмічна можливість розв'язання такої задачі встановлюється наступною теоремою:

Теорема (12). Для мов типу 3 існує алгоритм, що дозволяє по заданій граматиці визначити, чи є вона однозначною. Для інших типів мов ця задача алгоритмічно нерозв'язна.

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

Наступні дві теореми ставляться до питання про існування істотно неоднозначних мов різних типів.

Теорема 13 (Хомского й Міллера, Шютценберже). Не існує істотно неоднозначних мов типів 0, 2^D*, 3; всі ці мови однозначно виведені.

Теорема 14 (Перуки). Існують істотно неоднозначні бесконтекстні мови.

Для мов типу 1 (контекстних) це питання не вирішене.

Перука довела, що бесконтекстні мови L= {а^пb^mа^P|п = m або п = Р} й L = {х|х = а^пb^та^п'b^т Vх = а^пb^та^пb^т'; п, п', т, т' ≥1} є істотно неоднозначними. Другий із цих мов породжується граматикою G = ({а, b}, {S, А, В, З, D}, S, Р), де Р включає наступні правила:

S→AB S→DC

A→aAa А→аВа

B→b B→b

C→bCb C→bDb

D→a D→a

Наступна теорема розглядає алгоритмічну можливість розв'язання розпізнавання істотної неоднозначності:

Теорема 15 (Гладкого). Не існує алгоритму для рішення задачі про те, чи є задана мова типу 2^D істотно неоднозначним. Однак у деяких випадках це питання може бути вирішений.

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

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

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

Вправи:

1. Три граматики — G₁, G₂, G₃ -задані відповідними правилами: P₁ = {А→х, А → Ах}, Р₂ = {А→х, А →хА}, Р₃ = {А →x, А →xАх}, де А -ціль граматики.

Визначити тип еквівалентності граматик G₁, G₂, G₃.

2. Нехай G=(V_T,V_H, P, S) граматика, що-породжує, де VT={a, b}, VH={A, S}, P = {A>ab, A>aSAb, S>bAb, SA>b, S> ?). Визначити тип рекурсивності правил граматики й показати, що ланцюжок ababbabb належить множині L(G).

3. Побудувати мови L(Gj), де j = 1, 2, 3, якщо схеми правил граматик G₁, G₂ й G₃ мають такий вигляд:

P_{1 =} {S→AB, S→ASB};

Р₂ = {S→АА, S→BB, S →ASA, S→BSB};

P₃={S→AS, S→BS, CABSC→САВАВС}.

Для кожної граматики визначити V_т, V_H, довжину висновків, тип правил, вид граматики.

4. Дано граматику G = ({А, В}, {S}, Р, S), де Р = {S→SA, SS→ABA}. Визначити, чи є G-граматика граматикою безпосередньо складових.

5. Нехай Vт = {А, B}. Показати, що V*_T = {А^пВ^пА^п/п≥1} є НС-язык.

6. Граматики G₁, G₂, G₃, G₄ задані правилами виду: Р₁={А→хВ, В→y, В→zВ};

Р₂ = {А→Ву, А→СВ, В→Вх, В→х, С→ х, С→хС);

Р₃={А→Сх, В→Агов, С→Вz, С→z, D→хЕ, Е→ух};

Р₄ = {А→Сх, В→Агов, С→Вz, С→ х, D→хЕ, Е→yz}.

Визначити для кожної із заданих граматик:

а) термінальний і нетермінальний словник;

б) однозначність граматики;

в) вид рекурсії синтаксичних елементів;

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

7. Дано граматику G= (V_т, V_н, Р, S), де Р = {А→аВ, А→b, В→Аа, В→b. Побудувати С-маркер для ланцюжків ааbа, ааbаа, аааbаа.

8. Нехай V_т = {а, b, з}. Побудувати С-маркер, що відповідає виводу S→аbАbВ→аbВаАbВ→аbSbаАbВ→аbсbаАbВ→ аbсbасаbbВ →аbсbасаbbаа.

9. Визначити, чи є однозначної граматика G= ({а,b, з, d, е} {S, А, В, С}, Р = {S→АВВ, А→ас, С→bс, В →d е), S).

10. Нехай V_т = {а, b, с). Для яких із множин, що нижче приводять, Р граматика G = (Vт, Vн, Р, S) є невизначеною:

а) Р={S→aSbс, S→з, S→b, А→bА, А→а};

б) Р = {S → а²Sа, S → аSа, S→а, S→Λ};

в) Р={S→аВс, S→b, В→аВ, В→Ва, В→с};

г) Р = (S→а, S→Sа, S→bBb, В→аВb, В→асb}.

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

Р₁{А→ АА, А→а};

Р₂{В→а^SВ, В→a}.

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