Формальні мови та їх завдання

1. Формальна мова та задача належності

Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом Фразою, або Ланцюжком у алфавіті X називається послідовність символів із X. Множина всіх скінченних слів у алфавіті X позначається X. Зауважимо, що вона нескінченна. Вона містить Порожнє слово – послідовність довжиною 0, позначену буквою e. Множину X\{e } позначимо X+, а слово вигляду Ww w, де слово W Із X+ записано N разів – Wn. Вважатимемо, що W0 = e.

Довільна підмножина множини X називається Формальною мовою. Далі в цьому розділі вона буде називатися просто Мовою.

Приклади

1. Множина всіх слів у алфавіті { A} позначається { A} = {e, A, Aa, Aaa, } = { An | N 0 }. { An| N–непарне} позначає множину, або мову слів непарної довжини в алфавіті { A}; обидві мови нескінченні.

2. Ідентифікатор є послідовністю букв і цифр, що починається буквою. Множина всіх ідентифікаторів у алфавіті X={ A, B, 1} нескінченна. Якщо записати їх за зростанням довжини, то початок буде таким: { A, B, A1, Aa, Ab, B1, Ba, bb, }.

Задача перевірки, чи належить слово W мові L, називається Задачею належності, або Проблемою слів. Як правило, множина L задається певним Скінченним описанням, що визначає не тільки її саму, а й структуру її елементів.

Задача належності розв'язується найчастіше шляхом перевірки, чи має слово відповідну структуру, тобто шляхом Синтаксичного аналізу, або Розпізнавання. Наприклад, структура всіх можливих синтаксично правильних Паскальпрограм визначається скінченною та відносно невеликою сукупністю БНФ. Саме на її основі будуються Синтаксичні аналізатори В трансляторах, тобто програми аналізу синтаксичної правильності вхідних програм.

Формальні мови розглядатимуться далі як мови, задані саме Скінченним описом. Отже, Головним у вивченні формальних мов стає засіб їх задання. У розділі 10 ми вже познайомилися з одним із них – це були БНФ та їх сукупності. Розглянемо ще деякі.

2. Регулярні операції, вирази та мови

Означимо Регулярні операції над мовами: об'єднання, катенацію та ітерацію. Нехай L1, L2, L позначають довільні мови в алфавіті X.

Вираз L1 L2 позначає Об'єднання L1 і L2 – мову { W| W L1 або W L2}. Наприклад, { A, Ab} { A, B, Ba}={ A, B, Ab, Ba}.

Катенацією слів V і W називається дописування W після V: Vw. Вираз L1 L2 позначає Катенацію мов – мову { Vw| V L1, W L2}. Так, за L1={ A, Bc}, L2={ X, Y} катенація L1 L2={ Ax, Bcx, Ay, Bcy}, за L1={ A, Ab}, L2={e, B} катенація L1 L2={ A, Ab, Abb}.

Від катенації походить Піднесення до степеня: L0={e }, Li= Li1 L за I0. Так, вираз {e, A, Aa}2 задає мову {e, A, Aa, Aaa, Aaaa}.

Вираз L позначає Ітерацію мови L – мову { Wi| W L за I 0}, тобто {e } L L2 . Зазначимо, що ітерація не подається жодним скінченним виразом з операціями катенації та і тому Не є похідною від них. Якщо в мові L є непорожнє слово, то мова L нескінченна. Наприклад, вираз { Ab} задає мову {e, Ab, Abab, Ababab, }, { A, B}{ A, B,1} – множину ідентифікаторів у алфавіті { A, B, 1}.

Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази , e та A при A X є Регулярними в алфавіті X і задають відповідно Регулярні мови , {e }, { A}. Якщо R1 і R2 – регулярні вирази, що задають регулярні мови L1 і L2, то вирази R1, R1+ R2, R1 R2, R1 є регулярними й задають відповідно регулярні мови L1, L1 L2, L1 L2, L1.

Очевидно, що кожна скінченна мова є регулярною, оскільки задається регулярним виразом як скінченне об'єднання одноелементних регулярних мов.

Множина регулярних мов, заданих усіма можливими регулярними виразами в алфавіті X, називається Класом регулярних мов над X.

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

Не всі мови є регулярними. Наприклад, мова вкладених дужок, задана БНФ

вклдуж::= | вклдуж ,

Є множиною { N N| N0}, яка не задається жодним скінченним регулярним виразом доведення можна знайти в [АУ]. Отже, розглянемо інші, потужніші засоби задання мов.

3. Граматики Хомського

Граматикою Хомського називається четвірка G = X, N, P, S. Тут

X – алфавіт означуваної мови, або множина Термінальних символів Терміналів.

N – множина Позначень понять мови, тобто Нетермінальних символів Нетерміналів.

P – множина Правил виведення Продукцій вигляду V ® w, де

V X N N X N, W X N

Тобто правий ланцюжок є довільною послідовністю терміналів і нетерміналів, а лівий містить принаймні один нетермінал.

S – Початковий нетермінал Із множини N, або Позначення головного поняття, яким позначаються слова мови.

Нетермінали записуються словами в дужках або великими латинськими буквами. Термінали за необхідності часом беруться в апострофи. Як і в мові БНФ, замість продукцій вигляду V ® w1 Ww2 і V ® w1 W2 записується продукція V ® w1[ W] W2, а замість продукцій V ® w1 U1 W2 і V ® w1 U2 W2 – продукція V1® W1 U1| U2 W2.

Приклад 3. Множину продукцій граматики

G1 ={ A, 1, 2 },

{ A, B, C, D },

{ A ® BC, A ® BD, A ® B, B ® A, C ® 1, D ® 2 },

A

Можна переписати у вигляді

{ A ® B [ C | D ], B ® A, C ® 1, D ® 2 }.

Як бачимо, продукції граматики дуже схожі на БНФ як за формою, так і за змістом – лише замість знака::= вживається ®. Проте в лівій частині їх продукцій може бути не поодинокий нетермінал, а цілий ланцюжок, у якому обов'язково є нетермінал. За рахунок такого узагальнення граматики виявляються більш потужним засобом задання мов, ніж системи БНФ, тобто існують мови, які задаються граматиками, але не задаються БНФ. Тепер опишемо спосіб, у який граматика G = X, N, P, S задає мову.

1. На множині слів об'єднаного алфавіту X N означається Відношення безпосередньої виводимості, позначене знаком G або , коли відомо, якою саме є G:

V G W, якщо V = X1 U X2, W = X1 Y X2, U ® Y P.

При цьому кажуть, що W безпосередньо виводиться з v Застосуванням продукції u ® y. Наприклад, у граматиці G1 із прикладу 21.3 BC aC Застосуванням продукції B ® a, AC a1застосуванням C ® 1.

2. На множині X N означається Відношення виводимості, позначене G або , коли відомо, якою саме є G: V W, якщо V= W або існує послідовність W1, W2, , Wn слів, де N 1, така, що V w1, W1 W2, , Wn1 Wn, Wn= W. Так, у граматиці G1 BC A1, оскільки BC aC, AC a1. Послідовність V w1 W2 Wn називається Виведенням Wn із V, а N – Довжиною виведення. Інколи довжину записують замість '' таким чином: V nw, наприклад, BC 2 A1.

3. Якщо S G W, то послідовність S W називається Виведенням слова w у граматиці G, а слово W – Вивідним. Так, слова A, BC, AC, A1 вивідні в граматиці G1.

4. Вивідні слова в алфавіті X називаються Породжуваними, а множина їх усіх – Мовою, що задається Породжується Граматикою G: L G = { W | W X та S W }.

Приклади

4. Граматика G1 із прикладу 21.3 задає мову { A, A1, A2 }.

5. Граматика

G2 = { A, , z, 0, , 9 }, { I, L, D },

{ I ® L | IL | ID, L ® A | | z, D ® 0 |... | 9 },

I

Породжує множину ідентифікаторів.

6. Граматика G3 = { , }, { S }, { S ® e | S }, S задає множину вкладених дужок { N N | N 0 }.

7. Граматика

G4 = { A, B, C }, { S, A, B, C},

{ S ® aSBC | AbC, CB ® BC, BB ® Bb, BC ® Bc, CC ® Cc },

S

Визначає мову { Anbncn | N 1 }.

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

{ A, 1, 2 }, { A }, { A ® A [ 1 | 2 ] }, A

Еквівалентна граматиці G1, граматика

{ A, , z, 0, , 9}, { I, C}, { I ® A||z C, C ® e | C A ||z|0||9}, I

– граматиці G2.

Є два види граматик з продукціями обмеженого вигляду, якими задаються регулярні мови, – це праволінійні та ліволінійні граматики. Праволінійною Ліволінійною називається граматика, всі продукції якої мають вигляд A ® w або A ® wB відповідно, A ® w або A ® Bw, де A, B – нетермінали, W X. Усі можливі праволінійні та ліволінійні граматики з термінальним алфавітом X породжують в точності клас регулярних мов над X. Це доводиться, наприклад, в [АУ].