WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Формальні мови та їх завдання - Реферат

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


Реферат на тему:
Формальні мови та їх завдання
1. Формальна мова та задача належності
Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом (фразою, або ланцюжком) у алфавіті X називається послідовність символів із X. Множина всіх скінченних слів у алфавіті X позначається X*. Зауважимо, що вона нескінченна. Вона містить порожнє слово - послідовність довжиною 0, позначену буквою . Множину X*{ } позначимо X+, а слово вигляду ww w, де слово w із X+ записано n разів - wn. Вважатимемо, що w0 = .
Довільна підмножина множини X* називається формальною мовою. Далі в цьому розділі вона буде називатися просто мовою.
Приклади
1. Множина всіх слів у алфавіті {a} позначається {a}* = { , 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. Вираз L1L2 позначає катенацію мов - мову {vw|v L1, w L2}. Так, за L1={a, bc}, L2={x, y} катенація L1L2={ax, bcx, ay, bcy}, за L1={a, ab}, L2={ , b} катенація L1L2={a, ab, abb}.
Від катенації походить піднесення до степеня: L0={ }, Li=Li-1L за i>0. Так, вираз { , a, aa}2 задає мову { , a, aa, aaa, aaaa}.
Вираз L* позначає ітерацію мови L - мову {wi|w L за i 0}, тобто { } L L2 . Зазначимо, що ітерація не подається жодним скінченним виразом з операціями катенації та і тому не є похідною від них. Якщо в мові L є непорожнє слово, то мова L* нескінченна. Наприклад, вираз {ab}* задає мову { ,ab,abab,ababab, }, {a,b}{a,b,1}* - множину ідентифікаторів у алфавіті {a, b, 1}.
Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази , та a при a X є регулярними в алфавіті X і задають відповідно регулярні мови , { }, {a}. Якщо r1 і r2 - регулярні вирази, що задають регулярні мови L1 і L2 , то вирази (r1), r1+r2, r1r2, r1* є регулярними й задають відповідно регулярні мови L1, L1 L2, L1L2, L1*.
Очевидно, що кожна скінченна мова є регулярною, оскільки задається регулярним виразом як скінченне об'єднання одноелементних регулярних мов.
Множина регулярних мов, заданих усіма можливими регулярними виразами в алфавіті X, називається класом регулярних мов над X.
Регулярні операції застосовні до будь-яких мов, а не тільки до регулярних. За означенням, застосування їх до регулярних мов породжує регулярні мови.
Не всі мови є регулярними. Наприклад, "мова вкладених дужок", задана БНФ
::= ( ) | ( ),
є множиною {(n)n|n>0}, яка не задається жодним скінченним регулярним виразом (доведення можна знайти в [АУ]). Отже, розглянемо інші, потужніші засоби задання мов.
3. Граматики Хомського
Граматикою Хомського називається четвірка G = (X, N, P, S). Тут
X - алфавіт означуваної мови, або множина термінальних символів (терміналів).
N - множина позначень понять мови, тобто нетермінальних символів (нетерміналів).
P - множина правил виведення (продукцій) вигляду v w, де
v ( X N )* N ( X N )* , w ( X N )*
тобто правий ланцюжок є довільною послідовністю терміналів і нетерміналів, а лівий містить принаймні один нетермінал.
S - початковий нетермінал із множини N, або позначення головного поняття, яким позначаються слова мови.
Нетермінали записуються словами в дужках або великими латинськими буквами. Термінали за необхідності часом беруться в апострофи. Як і в мові БНФ, замість продукцій вигляду v w1ww2 і v w1w2 записується продукція v w1[w]w2, а замість продукцій v w1u1w2 і v w1u2w2 - продукція 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, … , wn-1==> wn, wn=w. Так, у граматиці G1 BC==> *a1, оскільки BC==> aC, aC==> a1. Послідовність v==> w1==> w2==> …==> wn називається виведенням wn із v, а n - довжиною виведення. Інколи довжину записують замість '*' таким чином: v==> nw, наприклад, BC ==> 2a1.
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 | ( 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 |C(a |…|z|0|…|9)}, I )
- граматиці G2.
Є два види граматик з продукціями обмеженого вигляду, якими задаються регулярні мови, - це праволінійні та ліволінійні граматики. Праволінійною (ліволінійною) називається граматика, всі продукції якої мають вигляд A w або A wB (відповідно, A w або A Bw), де A, B - нетермінали, w X*. Усі можливі праволінійні та ліволінійні граматики з термінальним алфавітом X породжують в точності клас регулярних мов над X. Це доводиться, наприклад, в [АУ].
Loading...

 
 

Цікаве