Формальні мови та їх завдання
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. Вираз L1L2 позначає катенацію мов – мову {vw|vÎ L1, wÎ L2}. Так, за L1={a, bc}, L2={x, y} катенація L1L2={ax, bcx, ay, bcy}, за L1={a, ab}, L2={e , b} катенація L1L2={a, ab, abb}.

Від катенації походить піднесення до степеня: L0={e }, Li=Li-1L за i>0. Так, вираз {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, 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 ® 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. Це доводиться, наприклад, в [АУ].
Случайные рефераты:
Реферати - Павло Архипович Загребельний
Реферати - Михайло Старицький
Реферати - Іван Котляревський
Реферати - Пісня у драмі-опері Івана Котляревського "Наталка Полтавка"
Реферати - До "280 річниці з дня народження Григорія Сковороди" (творча робота)
Реферати - Іван Карпенко-Карий
Реферати
  • Всі реферати
  • Архітектура
  • Астрономія, авіація
  • Аудит
  • Банківська справа
  • Безпека життєдіяльності
  • Біографія, автобіографія
  • Біологія
  • Бухгалтерський облік
  • Військова кафедра
  • Географія
  • Геологія
  • Гроші і кредит
  • Державне регулювання
  • Діловодство
  • Екологія
  • Економіка підприємства
  • Економічна теорія
  • Журналістика
  • Іноземні мови
  • Інформатика, програмування
  • Історія всесвітня
  • Історія України
  • Історія економічних вчень
  • Краєзнавство
  • Кулінарія
  • Культура
  • Література
  • Макроекономіка
  • Маркетинг
  • Математика
  • Медицина та здоров'я
  • Менеджмент
  • Міжнародні відносини
  • Мікроекономіка
  • Мовознавство
  • Педагогіка
  • Підприємництво
  • Політологія
  • Право
  • Релігієзнавство
  • Промисловість
  • Сільське господарство
  • Сочинения на русском
  • Соціологія
  • Литература на русском
  • Страхування
  • Твори
  • Фізика
  • Фізична культура
  • Філософія
  • Фінанси
  • Хімія
  • Цінні папери
  • Логіка
  • Туризм
  • Психологія