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

Реферат на тему:

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

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

Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом (фразою, або ланцюжком) у алфавіті X називається послідовність символів із X. Множина всіх скінченних слів у алфавіті X позначається X*. Зауважимо, що вона нескінченна. Вона містить порожнє слово — послідовність довжиною 0, позначену буквою xF065. Множину X*{xF065 } позначимо X+, а слово вигляду wwxF0BC w, де слово w із X+ записано n разів — wn. Вважатимемо, що w0 = xF065 .

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

Приклади.

1. Множина всіх слів у алфавіті {a} позначається {a}* = {xF065, a, aa, aaa, … } = { an | n xF0B3 0 }. {an|n-непарне} позначає множину, або мову слів непарної довжини в алфавіті {a}; обидві мови нескінченні.xF0E7.

2. Ідентифікатор є послідовністю букв і цифр, що починається буквою. Множина всіх ідентифікаторів у алфавіті X={a, b, 1} нескінченна. Якщо записати їх за зростанням довжини, то початок буде таким: { a, b, a1, aa, ab, b1, ba, bb, xF0BC }.xF0E7.

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

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

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

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

Вираз L1xF0C8 L2 позначає об «єднання L1 і L2 — мову {w|wxF0CE L1 або wxF0CE L2}. Наприклад, {a, ab}xF0C8 {a, b, ba}={a, b, ab, ba}.

Катенацією слів v і w називається дописування w після v: vw. Вираз L1L2 позначає катенацію мов — мову {vw|vxF0CE L1, wxF0CE L2}. Так, за L1={a, bc}, L2={x, y} катенація L1L2={ax, bcx, ay, bcy}, за L1={a, ab}, L2={xF065, b} катенація L1L2={a, ab, abb}.

Від катенації походить піднесення до степеня: L0={xF065 }, Li=Li-1L за i>0. Так, вираз {xF065, a, aa}2 задає мову {xF065, a, aa, aaa, aaaa}.

Вираз L* позначає ітерацію мови L — мову {wi|wxF0CE L за ixF0B3 0}, тобто {xF065 }xF0C8 LxF0C8 L2xF0C8 xF0BC. Зазначимо, що ітерація не подається жодним скінченним виразом з операціями катенації та xF0C8 і тому не є похідною від них. Якщо в мові L є непорожнє слово, то мова L* нескінченна. Наприклад, вираз {ab}* задає мову {xF065, ab, abab, ababab, xF0BC }, {a, b}{a, b,1}* - множину ідентифікаторів у алфавіті {a, b, 1}.

Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази xF0C6, xF065 та a при axF0CE X є регулярними в алфавіті X і задають відповідно регулярні мови xF0C6, {xF065 }, {a}. Якщо r1 і r2 — регулярні вирази, що задають регулярні мови L1 і L2, то вирази (r1), r1+r2, r1r2, r1* є регулярними й задають відповідно регулярні мови L1, L1xF0C8 L2, L1L2, L1*.

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

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

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

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

<�вкл-дуж> := () | (<�вкл-дуж>),.

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

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

D.

F.

^.

" .

d.

f.

x20AC.

‚.

".

x00A8.

®.

x00B2.

E.

I.

O.

" .

O.

O.

Oe.

e.

i.

th.

;

" .

v.

x.

x02DC.

x0161.

x0153.

¦

x00A8.

®.

°.

x00B4.

x00B8.

¼.

A.

Oe.

O.

U.

a.

a.

ae.

ae.

o.

oe.

o.

u.

ue.

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

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

N — множина позначень понять мови, тобто нетермінальних символів (нетерміналів).

P — множина правил виведення (продукцій) вигляду vxF0AE w, де.

v xF0CE (X xF0C8 N)* N (X xF0C8 N)*, w xF0CE (X xF0C8 N)*.

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

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

Нетермінали записуються словами в дужках <> або великими латинськими буквами. Термінали за необхідності часом беруться в апострофи. Як і в мові БНФ, замість продукцій вигляду vxF0AE w1ww2 і vxF0AE w1w2 записується продукція vxF0AE w1[w]w2, а замість продукцій vxF0AE w1u1w2 і vxF0AE w1u2w2 — продукція v1xF0AE w1(u1|u2)w2 .

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

G1 =({ a, 1, 2 },.

{ A, B, C, D },.

{ A xF0AE BC, A xF0AE BD, A xF0AE B, B xF0AE a, C xF0AE 1, D xF0AE 2 },.

A).

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

{ A xF0AE B [ C | D ], B xF0AE a, C xF0AE 1, D xF0AE 2 }.xF0E7.

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

1. На множині слів об «єднаного алфавіту (XxF0C8 N)* означається відношення безпосередньої виводимості, позначене знаком xF0DE G (або xF0DE, коли відомо, якою саме є G):

v xF0DE G w, якщо v = x1 u x2, w = x1 y x2, u xF0AE y xF0CE P.

При цьому кажуть, що w безпосередньо виводиться з v застосуванням продукції uxF0AE y. Наприклад, у граматиці G1 із прикладу 21.3 BCxF0DE aC застосуванням продукції BxF0AE a, aCxF0DE a1застосуванням CxF0AE 1.

2. На множині (XxF0C8 N)* означається відношення виводимості, позначене xF0DE *G (або xF0DE *, коли відомо, якою саме є G): vxF0DE *w, якщо v=w або існує послідовність w1, w2, …, wn слів, де nxF0B3 1, така, що vxF0DE w1, w1xF0DE w2, …, wn-1xF0DE wn, wn=w. Так, у граматиці G1 BCxF0DE *a1, оскільки BCxF0DE aC, aCxF0DE a1. Послідовність vxF0DE w1xF0DE w2xF0DE… xF0DE wn називається виведенням wn із v, а n — довжиною виведення. Інколи довжину записують замість «* «таким чином: vxF0DE nw, наприклад, BC xF0DE 2a1.

3. Якщо SxF0DE G*w, то послідовність SxF0DE… xF0DE w називається виведенням слова w у граматиці G, а слово w — вивідним. Так, слова A, BC, aC, a1 вивідні в граматиці G1.

4. Вивідні слова в алфавіті X називаються породжуваними, а множина їх усіх — мовою, що задається (породжується) граматикою G: L (G) = {w | wxF0CE X* та S xF0DE * w }.

Приклади.

4. Граматика G1 із прикладу 21.3 задає мову { a, a1, a2 }.xF0E7.

5. Граматика.

G2 = ({ a, …, z, 0, …, 9 }, { I, L, D },.

{ I xF0AE L | IL | ID, L xF0AE a | … | z, D xF0AE 0 | … | 9 },.

I).

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

6. Граматика G3 = ({ (,) }, { S }, { S xF0AE xF065 | (S) }, S) задає множину «вкладених дужок «{ (n)n | n xF0B3 0 }.xF0E7.

7. Граматика.

G4 = ({ a, b, c }, { S, A, B, C},.

{ S xF0AE aSBC | abC, CB xF0AE BC, bB xF0AE bb, bC xF0AE bc, cC xF0AE cc },.

S).

визначає мову { anbncn | n xF0B3 1 }.xF0E7.

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

({ a, 1, 2 }, { A }, { A xF0AE a [ 1 | 2 ] }, A).

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

({a, …, z, 0, …, 9}, {I, C}, {I xF0AE (a|…|z)C, C xF0AE xF065 |C (a |…|z|0|…|9)}, I).

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

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