Дискретна математика

що виведене перед цим міститься підслово α, то виконується ця підстановка і далі вибирається правило з позначкою, що належить множині Y. Якщо ж не можна застосувати правило α → β , то далі вибирається правило із з позначкою, що належить множині N.

Програмна граматика, ядра правил виведення в якій відповідають обмеженням безконтекстної граматики Хомського, називається безконтекстною програмною граматикою.

Аналогічно вводяться регулярна і контекстно-залежна програмні граматики.

Доведено, що програмна контекстно-вільна граматика породжує контекстно-залежну мову. Наприклад. Контекстно-залежна грамматика G2, що розглянута нами раніше, породжує контекстно-

залежну мову, слова якої мають вигляд

0...01...10...0, n 2.

Приклад породження слова 110011 в цій програмній граматиці: n dk 1c0k 1c000k 1c0k 11d00k 11d0011k 11d0011dk 110011dk110011

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

Як бачимо, створення слова складної структури в програмних граматиках базується на ідеї алгоритмічних мов програмування – застосуванні команд у певному порядку (у нас правил виведення). З тією ж метою можна розглянути застосування й інших відомих методів. Зараз розглянемо застосування ідеї багаторазового дублювання послідовності символів.

76.Індексні гр м тики

81

xi D, і = , якщо xi E, i = 1,2, … , n.

Приклад. Індексна граматика має вигляд G = ({d0,d1,d2,d3,d4}, {0,1}, {f, g},P,d0), де множина Р містить такі правила:

d0→d1g d1→d1f d1→d2d3d4 d2f→0d2 d3f→1d3 d4f→0d4 d2g→0 d3g→1 d4g→0

Приклад виведення слова 000111000 в цій індексній граматиці:

d0 d1 g d1 fg d1 ffg d2 ffgd 3 ffgd 4 ffg 0d2 fgd 3 ffgd 4 ffg ... 000d3 ffgd 4 ffg ... 000d3 ffgd 4 ffg 0001d3 fgd 4 ffg 00011d3 gd4 ffg ... 000111000

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

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

77.Дерев виведення

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

Означення. Нехай G = <D, E, P, d0> - контекстно-вільна граматика. Деревом виведення (розбору) в G назвемо позначене дерево G0 з впорядкованими шляхами від кореня до листків, якщо:

-корінь дерева G0 позначений d0;

-якщо корінь дерева має єдиного нащадка , то цей нащадок утворює піддерево з однієї вершини і d0 - правило з Р;

- якщо піддерева G1, G2,…, Gк мають загального пращура d0, корінь Gі позначений Хі, то d0 Х1 … Хк - правило з Р, причому Gі повинне бути деревом виведення в граматиці Gі = <D,E,P,Хі>, якщо Хі D і складатися з єдиної вершини, якщо Хі E.

Приклад. У відомій нам граматиці для породження мови { , 01,0011,000111,…} деревами виведення будуть:

г)

Означення. Кроною дерева виведення назвемо слово, утворене конкатенацією позначок листків зліва направо.

Наприклад, крона дерева виведення, наведеного на рис. б) - ; рис. в) - 0011; рис. г) - 01. Означення. Перерізом S дерева виведення G0 назвемо таку множину його вершин, що:

-ніякі дві вершини S не лежать на одному шляху в G0;

-додавання будь-якої вершини G0 до S порушує попередню умову. Приклад. Для в) перерізами будуть:

S1 = {0, 0, , 1,1}

S2= {0, 0, d1, 1,1}

S3= {0, d1, 1}

82

Означення. Кроною перерізу S дерева виведення G0 назвемо конкатенацію (зліва направо) позначок вершин S.

Для перерізу S1 кроною буде 0011, перерізу S2 - 00d111, перерізу S3 - 0 d11.

Тепер наша мета полягає в тому, щоб досить незручне поняття ―виводимості" замінити зручним для нас поняттям ―дерево виведення". Для цього треба довести їх еквівалентність, що допоможе зробити наступна

Теорема 4.1. Нехай G = <D,E,P,d0> - КВ-граматика. Слово виводиться в G тоді і тільки тоді, коли в G існує дерево виведення з кроною .

Доведення.

а) прямої теореми. Нехай, 0,…, n, де n = - вивід слова з d0 в граматиці G. Покажемо, що в G можна побудувати дерево виведення з кроною , причому 0,…, n-1 - деякі з крон перерізів.

Побудуємо згідно 0,…, n послідовність дерев виведення:

-G0 складається з єдиної вершини d0;

-Gi+1 будується з Gi наступним чином: нехай i+1 отримана з i = idi i, де i, i - слова в алфавіті

(D E), di D, застосуванням правила виведення di x1 x2 xk і має вигляд i x1 x2 xk i ; тоді Gi+1 виходить додаванням до листка di дерева Gi нащадків x1 x2 xk .

Очевидно, що крона Gi+1 має вигляд i+1, а Gn буде деревом виведення, що доводить пряму теорему. б) оберненої теореми. Нехай G0 - дерево виведення в граматиці G з кроною . Покажемо, що слово

виводиться в G. Побудуємо послідовність перерізів S0, S1,…, Sn дерева таким чином:

-S0 містить тільки корінь дерева, тобто d0;

-Sі+1 визначається по Sі (0 i <n) заміною однієї нетермінальної вершини її прямими нащадками;

-Sn – крона Gn.

Очевидно, щонайменше одну таку послідовність ми можемо побудувати. Але тоді крона i+1 перерізу Sі+1 отримується за допомогою правила виведення, яке належить множині Р. Іншими словами 0,…, n - вивід слова в граматиці G. Теорема доведена.

І ще один термін. Якщо граматика G є контекстно-вільною граматикою, то в доведенні оберненої теореми можна завжди замінювати найлівіший або найправіший нетермінали, якщо їх декілька в i, (i = 1,…,n-1). Тоді вивід назвемо відповідно лівим (правим), а слово лівовиводимим (правовиводимим).

78.Некорисні і недосяжні символи

Вже зараз можна сказати, що було б зручно якби граматика не мала деяких небажаних властивостей, наприклад неоднозначності. Природно, що граматику G можна модифікувати до граматики Gm за умови

L(G) = L(Gm).

Розглянемо такі перетворення граматик.

Означення. Нехай G = <D, Е, Р, d0> - контекстно-вільна граматика. Символ X D назвемо некорисним в граматиці G, якщо в ній немає виводу

де β, , E*.

Приклад. В граматиці G = <{d0,d1}, {0,1}, Р, d0>, де множину Р складають такі правила:

d0→0 d1→1

некорисним є нетермінал d1.

Означення. Нехай G = <D, Е, Р, d0> - контекстно-вільна граматика. Символ X E назвемо некорисним в граматиці G, якщо в ній немає виводу

*

d0 X , де β, E*.

G

В наведеній в попередньому прикладі граматиці G некорисним є термінал 1.

Означення. Нехай G = <D, Е, Р, d0> - контекстно-вільна граматика. Символ X D E назвемо недосяжним в граматиці G, якщо Х не з'являється в жодному слові, що виводиться в граматиці G.

Зазначимо, що крім можливості приведення граматики G до більш зручного вигляду, виявлення того факту, що d0 - некорисний, має важливе значення для розв'язання проблеми порожнечі мови L(G). Якби ми мали алгоритм, результатом роботи якого було б "так" при виконанні умови

83

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

Алгоритм ПП.

Крок 1. N0 = , i = 1;

Крок 2. Ni = {dj dj→α P і α (Ni-1 E)*} Ni -1;

Крок 3. Якщо Ni Ni-1, то i = i +1 і перехід на крок (2). Інакше Ni = N; Крок 4. Якщо d0 N, то видати ―Так", інакше видати ―Ні".

Очевидно, алгоритм зупиниться щонайбільше після n+1 повторів кроку 2, якщо множина не терміналів граматики містить n символів.

Теорема 4.2. Алгоритм ПП дає відповідь "так" тоді і тільки тоді, коли існує слово таке, що E* і d0 * в граматиці G.

Доведення. Воно складається із наступних двох частин:

1. Доведемо індукцією по i, що для кожного нетермінала dk множини N існує таке термінальне слово, dk * в граматиці G.

Для N0 це очевидно.

Індуктивне припущення: твердження частини 1 виконується для i.

Нехай dk Ni +1. Якщо при цьому dk Ni, то доведення тривіальне. Якщо ж dk Ni +1\Ni, то існує правило dk → X1X2…Xt, де кожен символ Xj належить або E, або Ni. Тоді для кожного Xj можна знайти таке слово j, що Xj → j (для Xj E це j = Xj, для Xj Ni це слово дає базис індукції). Тоді легко зрозуміти, що

dk X1X2…Xt * 1X2…Xt * ... 1… t

2.Доведемо індукцією по n, що для нетермінала dk, такого що dk n в граматиці G, виконується dk

Ni для деякого i.

Для n = 1 це очевидно.

Індуктивне припущення: твердження частини 2 виконується для n.

Нехай dk n+1 в граматиці G. Тоді dk X1X2…Xt n в граматиці G, де = 1… t – таке слово, що Xj nj j для кожного і nj n.

Якщо Xj N, то Xj Nij для певного іj. Якщо Xj E, то іj = 0. Нехай і = 1 + max{і1,…,іt}. Тоді за означенням dk Ni. Прийнявши dk = dk, отримаємо твердження теореми 4.2. Теорема доведена.

Таким чином, проблема порожнечі мови L(G), породжуваної довільною контекстно-вільною граматикою G розв‘язувана.

Приклад.

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

Алгоритм позбавлення від недосяжних символів (НДС).

Крок 1. V0 ={d0}, i=1;

Крок 2. Vi = {X в P є dj → αXβ і dj Vi-1} Vi-1;

Крок 3. Якщо Vi Vi-1, то i=i+1 і перехід на крок 2, інакше

D/ = Vi D, E/ = Vi E.

Граматика G' = <D1/,E1/,P1/,d0>, де множина Р/ складається тільки з тих правил з множини Р, що містять тільки символи з множини Vi, не містить недосяжних символів, що легко довести. Завершуваність роботи алгоритму НДС гарантується тим, що може бути лише скінченна кількість кроків 2.

А тепер наведемо алгоритм усунення некорисних символів (НКС). Алгоритм позбавлення від некорисних символів (НКС).

Крок 1. Застосовуючи алгоритм ПП, отримаємо множину N.

Крок 2. Формуємо граматику G1 = <D N,E,P1,d0>, де множина P1 складається тільки з тих правил з множини Р, які містять символи з множини N E.

Крок 3. Застосовуємо до граматики G1 алгоритм НДС і отримуємо граматику G/1 = <D/1,E/1,P/1,d0>. Теорема 4.3. Граматика G/1 = <D/1,E/1,P/1,d0> не містить некорисних символів і L(G) = L(G/1). Доведення. Складається з наступних двох частин:

1. Доведемо, що G/1 не містить некорисних символів, розглянувши два можливі випадки: а) вивід

84

для деяких β, E* можливий, але виводу із X термінального слова в алфавіті із E/1 не існує. В цьому випадку символ X вилучається на кроках 1-2 алгоритму НКС;

2. Доведення L(G) = L(G/1) очевидне. Теорема доведена.

Внаведеній в попередньому прикладі граматиці G некорисним є термінал 1. Приклад.

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

Алгоритм приведення довільної контекстно-вільної граматики G до граматики, яка не вкорочує (НГ). Нехай маємо контекстно-вільну граматику G = <D, Е, Р, d0>.

Крок 1. Побудувати множину D0 ={di di N і di G+ }. Крок 2. Побудувати множину P/ таким чином:

а) якщо di→α0β1α1β2…βkαk P, k 0 і βi D0 для 1 i k, але жоден символ з αj (0 j k) не належить D0, включити в Р/ всі правила вигляду di→α0X1α1X2…Xkrαk, де Xi є або βi, або , але не включати в Р/ правило di → ;

б) якщо d0 D0, то включити в Р' правила:

d0/→

d0/→d0, де d0/ D/ = D/ {d0/}. Інакше D' = D0 і d/ = d0.

(3) Сформувати граматику G' = <D/,E/,P/,d0/ >.

Легко довести, що в результаті роботи алгоритму НГ отримуємо граматику G', яка не вкорочує,

причому L(G) = L(G').

Приклад. В граматиці G = <{d0,d1}, {0,1}, Р, d0> множину Р складають такі правила: d0→0d01d0

d0→1d00d0 d0→ .

Множину D0 складає символ d0.

Тоді побудуємо множину P/:

d0/→d0 d0/→

d0→0d01d0 d0→1d00d0 d0→0d01 d0→01d0 d0→01 d0→1d00 d0→10d0

d0→10

Отже, ми навчилися позбавляти граматики некорисних символів і правил виведення вигляду di → . Ми маємо алгоритми для боротьби з некорисними символами і правилами виведення вигляду di → . Тепер розглянемо як боротися з циклами. Наприклад, якщо є така множина правил виведення:

di→dj0 dj→di1 di→0 dj→1

то маємо цикл. Пізніше, розглядаючи нормальні форми, ми побачимо, що наявність циклів не дозволяє визначити потрібний порядок на множині не терміналів. Цикл можна вилучити, скориставшись підстановкою на множині правил, наприклад у всі правила замість dj підставити праві частини правил виведення, в яких dj складає ліву частину і, таким чином, ввести правила di→di10 і di→10. Крім того, в граматиці всі правила вигляду di → diei після видалення циклів треба замінити на di → eidi.

79.Норм льн форм Хомського

Означення. Контекстно-вільна граматика G = <D, Е, Р, d0> називається граматикою в нормальній формі Хомського, якщо кожне її правило виведення має вигляд:

(1)di→djdl, де di,dj,dl D, або

(2)di→ei, де di D, ei E, або

85

(3) d0→ , якщо L(G).

Причому d0 не зустрічається ніде в правій частині правил виведення.

Існує алгоритм, з допомогою якого будь-яку контекстно-вільну граматику можна представити в нормальній формі Хомського.

Нехай G = <D, Е, Р, d0> - контекстно-вільна граматика.

Крок 1. Включаємо в множину Р' кожне правило виведення вигляду di→ei із множини Р. Крок 2. Включаємо в множину Р' кожне правило виведення вигляду di→djdl із множини Р. Крок 3. Включаємо в множину Р' правило d0→ , якщо воно було в множині Р.

Крок 4. Для кожного правила виведення із множини Р вигляду di → x1x2…xk, k>2 включаємо в множину Р' такі правила:

di → x1/ x2…xk

x2…xk → x2 x3…xk

…

xk-2,xk-1xk → xk/-2 xk-1xkxk-1xk → x/k-1x/k,

де хi/ = хi , якщо хi D;

х/i - новий нетермінал, якщо хi E;хi...хk - новий нетермінал.

Крок 5. Для кожного правила виведення із множини Р вигляду di → x1x2, де хоча б один із символів х1 і х2 належить алфавіту Е, включаємо в множину Р' таке правило виведення:

di → x/1x/2, де хi/ = хi , якщо хi D;

х/i - новий нетермінал, якщо хi E. Крок 6. Додати до множини Р' правило:

х' х для кожного нового не терміналу, що введений в правилах кроків 4 і 5.

Крок 7. Граматика <D', Е, Р/, d0>, де D' = D D0 (тут Do- множина нових нетерміналів), є граматикою в нормальній формі Хомського.

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

Приклад. Граматика G = <D, Е, Р, d0>, де множина Р містить такі правила:

d2→d1d0 d2→e2

є контекстно-вільною граматикою. Приведемо її до нормальної форми Хомського. Включаємо в множину Р' всі правила, що відповідають умовам НФ Хомського:

d0→d2d1

d2→e2 d2→d1d0

Замість правила виведення d0→e1d1d2 включаємо в множину Р' такі правила:

Тут e/1 і d1d2 - нові не термінали.

Замість правила виведення d1 → d2d2d2 включаємо в множину Р' правила:

Залишається початковий символ d0 в правій частині одного з правил. Тому додамо правило виведення d3→d0 (6). Граматикою в нормальній формі Хомського є граматика:

G = {d0,d1,d2,d3,e/1, d1d2 , d2d2 },{e1,e2},P/,d3 , множина правил виведення якої P/ включає правила множин (2) - (6).

86

80.Норм льн форм Грейб х

У зв‘язку з тим, що ця нормальна форма побудована на праворекурсивності, введемо необхідні поняття. Означення. Нетермінальний символ di D граматики G = <D, Е, Р, d0> назвемо рекурсивним, якщо

*

d i d i , причому не виконується умова

G

Якщо α = , то di – ліворекурсивний символ. Якщо β = , то di – праворекурсивний символ. Визначення. Назвемо контекстно-вільну граматику, що має хоча б один ліворекурсивний

(праворекурсивний) нетермінал ліворекурсивною (праворекурсивною). Назвемо граматику рекурсивною, якщо її нетермінали, крім може бути початкового символу d0, рекурсивні.

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

Означення. Контекстно-вільна граматика називається граматикою в нормальній формі Грейбах,

якщо в ній немає правил виведення вигляду di → , крім d0→ , і кожне правило, крім d0→ , має вигляд di→

ei , де ei Е, D*.

Алгоритм приведення контекстно-вільної граматики до нормальної форми Грейбах:

1.Задати на множині D мінімальний порядок такий, що кожне di-правило починається або з терміналу, або з нетерміналу dj такого, що di < dj.

2.Впорядкувати D = <d1,...,dn> так, що d1<d2<…<dn. i = n.

3.Якщо i = 0, то перейти на крок 5, інакше замінити правило di→djα, j>i на правила

di → β1α

……….

di → βnα, де dj → β1,…,dj → βm – всі dj - правила.

4.і = i -1 і перехід на крок 3.

5.У кожному правилі di → eix1…xk замінити хj E новим нетерміналом d/j.

6.Додати для кожного нового нетермінала х/j правило х/j → xj.

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

Якщо в граматиці G є, щонайменше, одне слово α L(G) таке, що воно є кроною двох і більше дерев виводу, то граматику G назвемо неоднозначною. Інакше вона однозначна. Таким чином, в неоднозначній граматиці повинно бути хоча б 2 різних виведення, наприклад, лівих і правих.

Приклад. Маємо граматику G = {d0, d1, d2, d3, d4}, {*, (, ), +, e1}, P, d0 , де множина Р містить такі правила виведення:

d0→d1 d0→d1d2 d2→+d1 d2→+d1d2 d1→d4 d1→d4d3 d3→*d4 d3→*d4d3 d4→(d0)

d4→e1

1.Впорядкуємо нетермінали наступним чином :d0 <d1<d2<d3<d4

2.Виконуємо крок 3 алгоритму почергово для кожного з не терміналів згідно визначеного порядку: 1) включаємо правила, ліву частину яких складає d4:

d4→e1 d4→(d0)

2) включаємо правила, ліву частину яких складає d3:

d3→*d4d3 d3→*d4

3) включаємо правила, ліву частину яких складає d2:

d2→+d1 d2→+d1d2

4) включаємо правила, ліву частину яких складає d1:

d1→(d0)d3

d1→ e1d3

87

d1→(d0)

d1→e1

Варто зазначити, що з двох правил для d1 ми отримали чотири правила за рахунок підстановки в праву їх частину правил для d4.

5) включаємо правила, ліву частину яких складає d0:

d0→(d0)d3

d0→ e1d3

d0→ (d0)

d0→e1

d0→(d0)d3d2 d0→ (d0)d2

d0→e1d3d2 d0→ e1d2

3.Потім скрізь термінал ), який входить у праві частини одержаних правил не першим символом, міняємо на не термінал )/ і вводимо нове правило

)/ ).

Таким чином, ми отримали нову граматику G/ = {d0, d1, d2, d3, d4, )/}, {*, (, ), +, e1}, P/, d0 , де множина Р/ містить такі правила виведення:

d4→e1 d4→(d0) d3→*d4d3 d3→*d4 d2→+d1 d2→+d1d2 d1→(d0)d3

d1→ e1d3

d1→(d0)

d1→e1

d0→(d0)d3

d0→ e1d3

d0→ (d0)

d0→e1

d0→(d0)d3d2 d0→ (d0)d2

d0→e1d3d2

d0→ e1d2 )/ ).

Контекстно-вільна граматика G/ знаходиться в нормальній формі Грейбах.

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

81.Регулярні вир зи т регулярні множини

Означення. Визначимо регулярну множину в алфавіті Е в такий спосіб.

1)– регулярна множина;

2){ } - регулярна множина;

3){ei} - регулярна множина;

4)якщо R і S – регулярні множини в алфавіті Е, то R S, R S, R* - також регулярні множини в алфавіті Е;

5)Т - регулярна множина в алфавіті Е тоді і тільки тоді, коли вона отримана застосуванням пунктів 1) –

4)даного означення.

Отже, множина регулярна в алфавіті Е, тоді і тільки тоді, коли або вона порожня, або містить тільки порожнє слово , або будь-який символ з алфавіту Е, або отримана з цих множин застосуванням скінченого числа операцій об'єднання, конкатенації й ітерації. Таким чином, усі скінчені множини регулярні.

Приклади регулярних множин в алфавіті Е = {0,1}.

а) ;

б) { }; б ) {0}; б ) {1}; в) {0,1} - як {0} {1};

г) {00,01,10,11} - як {0}{0} {0}{1} {1}{0} {1}{1};

д) { ,01,0101,010101,...} - як ({0}(1})*;

88

е) { ,0,00,..} - як ({0})*;

ж) { ,000111,000111000111,000111000111000111,…} - як ({0}({0}{0}{1}{1}{1})*;

з) { ,0,1,00,01,10,11,000,001,010,100,011,101,110,111,..} - як ({0} {1})*.

Щоб не виникло враження, що довільна нескінченна множина, елементами якої є послідовності 0 і 1 є регулярною множиною, нагадаємо наведений у розділі 1 приклад нескінченої множини {01,0011,000111,...}, що не є регулярною, і рекомендуємо читачеві звернутись до наведених у тому ж розділі міркувань, що обґрунтовують цей висновок.

Нагадаємо означення регулярних виразів. Означення регулярних виразів:

1)– регулярний вираз, що позначає регулярну множину ;

2)- регулярннй вираз, що позначає регулярну множину { };

3)ei - регулярний вираз, що позначає регулярну множину {ei}, якщо ei Е;

4)якщо r і s - регулярні вирази, що позначають відповідно регулярні множини R і S, то (r + s), (rs),

(r)* - регулярні вирази, що позначають відповідно регулярні множини R S, RS, R*;

5) t – регулярний вираз тоді і тільки тоді, коли це випливає з пунктів 1) - 4) цього означення. Наприклад, регулярний вираз (01) позначає регулярну множину {01}, регулярний вираз (010) - регулярну

множину {010}, регулярний вираз (0 + 1)* - регулярну множину {0, 1}*, регулярний вираз (e1 + e2)(e1 + e2 + e3 + e4)* - регулярну множину слів, складених із символів e1, e2, e3, e4, які розпочинаються з символу e1 чи e2.

Як і раніше дужок у регулярних виразах будемо позбуватися шляхом застосування пріоритету операцій, використовувати введені відношення рівності регулярних множин і виразів. Нагадаємо, що кожному регулярному виразу відповідає регулярна множина, а для кожної регулярної множини може існувати множина регулярних виразів, що позначає її. Важливі рівності регулярних виразів дає доведена в розділі 1 теорема.

82.Пр волінійні гр м тики

Теорема 4.4 Мова є регулярною множиною тоді і тільки тоді, коли вона є регулярною.

Доведення. а) необхідність. Спочатку доведемо, що , { }, {ei} для усіх ei Е, є регулярними мовами. Для цього розглянемо наступні автоматні граматики:

G1 = {d0}, E, , d0 - очевидно L(G1) = ;

G2 = {d0}, E, {d0 }, d0 - очевидно L(G2) = { }; G3 = {d0}, E, {d0 ei}, d0 - очевидно L(G2) = {ei}.

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

Нехай мови L1 і L2 регулярні. Тоді існують регулярні граматики G4 = D1, E, P1, d 0 і G5 = D2, E, P2, d 0 такі, що L1 = L(G4) і L2 = L(G5). Тоді L1 L2 - регулярна множина. Доведемо, що L1 L2 - регулярна

мова.

Розглянемо граматику G6 = D1 D2 {d 0}, E, P1 P2 {d 0 d 0, d 0 d 0}, d 0 . Очевидно, це - праволінійна граматика, а L(G6) - регулярна мова. Тут символ d 0, який не належить ні множині D1, ні множині D2, - новий нетермінальний символ. Залишається довести, що

Тоді для кожного виводу d 0 * слова в граматиці G6 існує або вивід d 0 * слова в граматиці G4, або вивід d 0 * слова в граматиці G5, тобто L(G4) L(G5) L(G6). І навпаки, якщо в

граматиці G4 існує вивід d 0 * слова або в граматиці G5 існує вивід d 0 слова , то в граматиці G6 існує вивід d 0 d 0, d 0 * або d 0 d 0, d 0 * , тобто L(G4) L(G5) L(G6). Таким чином, L(G4) L(G5) = L(G6).

L1L2 - регулярна множина. Доведемо, що L1L2 - регулярна мова.

Розглянемо граматику G7 = D1 D2, E, P3, d 0 , множина правил виведення P3 якої формується в такий спосіб:

1)якщо di dj P1, то di dj P3;

2)якщо di P1, то di d 0 P3;

3)усі правила множини P2 належать множині P3.

Якщо виводиться слово у граматиці G4, то виводиться слово d 0 в граматиці G7. А якщо виводиться слово у граматиці G5, то виводиться слово в граматиці G7. Тоді L(G4) L(G5) L(G7). Нехай слово виводиться в граматиці G7 з початкового символу d 0. Але тоді виводиться в граматиці G7 підслово d 0 і

виводиться з символу d 0 слово такі, що = . Але ці правила потрапили в граматику G7 за допомогою

кроків 1) і 2). Тоді L(G4) L(G5) L(G7). Звідси L(G4) L(G5) = L(G7).

І, нарешті, L1* - регулярна множина. Доведемо, що L1* - регулярна мова. Розглянемо граматику G8 =D1 {d 0}, E, P4, d 0 , причому d 0 D1, а множина P4 формується в такий спосіб:

1)якщо di dj P1, то di dj P4;

2)якщо di P1, то di d 0, di P4;

3)d 0 d 0, d 0 .

89

Тепер легко довести, що L(G8) = (L(G4))*.

Отже, якою б скінченою кількістю операцій об‘єднання, конкатенації та ітерації ми не скористалися над регулярними мовами , { }, {ei}, де ei E, завжди результатом буде регулярна мова.

б) достатність. Нехай G = D, E, P, d0 - праволінійна граматика. Необхідно довести, що вона породжує регулярну множину.

Слова породжуються в граматиці G за допомогою правил виведення вигляду:

1)di dj, E*;

2)di , E*.

Породження термінального слова тоді можливе, якщо існує скінчена послідовність Di правил

виведення :

d0 i1 di1 ,di1 i2 di2 ,...,din 1 in ,

де всі правила різні. Через те, що граматика G включає скінчену множину правил P, то якщо мова L(G)

не порожня, такі послідовності повинні існувати. З іншого боку, нескінченних послідовностей такого вигляду для граматики G не існує.

Доведемо обернену теорему індукцією по числу послідовностей демонструвати послідовності у виді маршрутів. Тоді для Di маршрут

в)

г)

д)

Ці послідовності задовольняють умовам:

1)перше правило має ліворуч d0;

2)останнє правило не має праворуч нетермінал;

90