Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом icon

Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом



НазваниеРеферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом
Дата конвертации22.01.2013
Размер56.13 Kb.
ТипРеферат



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

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

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  ( XN )* N ( XN )* , w  ( XN )*

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

^ 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 },

{ ABC, ABD, AB, Ba, C  1, D  2 },

A )

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

{ AB [ C | D ], Ba, C  1, D  2 }.

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

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

vG w, якщо v = x1 u x2 , w = x1 y x2 , uyP.

При цьому кажуть, що 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, наприклад, BC2a1.

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 },

{ IL | 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, CBBC, bBbb, bCbc, cCcc },

S )

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

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

( { a, 1, 2 }, { A }, { Aa [ 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. Це доводиться, наприклад, в [АУ].




Похожие:

Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconРеферат на тему: Лексика мови Паскаль та загальний вигляд програми
Кожна мова починається з алфавіту – скінченної множини символів. Алфавіт мови Паскаль складають
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconРеферат на тему: Тип символів та інші перелічувані
Нарешті ми розглянемо останній з базових типів – тип символів. Множина символів, представних у сучасному комп'ютері, як правило,...
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconРеферат на тему: проблема української мови суржик
Скажімо, “для хатнього вжитку” може використовуватися певна регіональна говірка чи мова, яку на роботі, в діловому мовленні, під...
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconПочаткові відомості про алгоритмічну мову Паскаль
Кожна мова починається з алфавіту – скінченної множини символів. Алфавіт мови Паскаль складають
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconЕлементи комбінаторики § Поняття множини. Операції над множинами
Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина...
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом icon"Українська мова державна мова України. Сучасний статус української літературної мови" Мова належить до так званих вторинних си­стем. Вона існує не сама по собі, а в людському суспільстві, похідним від якого вона є
Українська мова – державна мова України. Сучасний статус української літературної мови”
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconEnd можна відмітити, тобто ідентифікувати, додати йому індивідуальне ім'я. Це ім'я називається міткою
Це ім'я називається міткою. У авторській версії мови мітками могли бути цілі сталі від 1 до 9999, у мові Турбо Паскаль до них додано...
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconЗвіт про виконання лабораторної роботи № На тему
Можливими значеннями змiнних типу "множина" є всi пiдмножини базового типу. Кiлькiсть елементiв множини може мiнятися вiд 0 до 256....
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconЛітературні норми слововживання
Адже перед словом усі рівні. Перед Словом рівні, як перед світом: перед небом, землею І сонцем І мова на кожний народ одна, яка всіх...
Реферат на тему: Формальні мови та їх завдання Формальна мова та задача належності Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом iconСтарослов'янська мова та її вплив на становлення української мови
Про це свідчить І наявність архаїчної лексики, І деякі фонетичні та морфологічні риси, які зберегла наша мова протягом віків. Давність...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы