UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 12

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваФормальні мови та їх завдання (реферат)
Авторdimich
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось1235
Скачало282
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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}* – множину ідентифікаторів у

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ