Курсова робота на тему: «ІЄРАРХІЯ МОВ ЗА ХОМСЬКИМ»

Зміст

 

Вступ    3

1. Основні поняття формальних мов та граматик    4

2. Редукційні та генераційні граматики    8

3. Класифікація за Хомським    19

Висновок    25

Література    26

Вступ

В даній роботі я задався метою як найширше розкрити питання ієрархії мов за Хомським.

Для якнайкращого викладу матеріалу я вирішив розпочати з загальних моментів, які допоможуть поступово ввійти в суть справи. Беру початок своєї роботи з розгляду такого питання як «основні поняття формальних мов та граматик», де спробую довести до Вас основні терміни, поняття та навести певні приклади, які допоможуть розуміти матеріал.

Продовжувати своє дослідження я буду намагатись з детального розгляду таких видів граматик, як редукційні і генераційні. Свою роботу організую за планом розгляду першого питання, тобто спочатку ознайомлюсь з загального огляду граматик в цілому, а вже після цього буду розпочинати заглиблення їх види та особливості. Також в цьому питанні спробую розглянути основні моменти в класифікації мов за Хомським, де хочу ознайомитись з класами мов, їхніми особливостями, та властивостями.

Далі спробую організувати свою роботу за напрямком вивчення саме класифікацій за Хомським. А саме класифікації мов та граматик. Також спробую ознайомитись з операціями які можна виконувати над формальними мовами, розглянути таке поняття як формальні системи, способи задання формальних граматик а також багато суміжних питань, які дозволять розібратися в даній темі в повному обсязі.

Сподіваюсь, що зможу якнайкраще розібратися в поставлених переді мною питаннях і достатньо зрозуміло і якомога більш вичерпно довести результати моєї роботи до Вашого відома.

1. Основні поняття формальних мов та граматик

У цьому розділі вводяться найбільш важливі з понять, якими оперує теорія автоматів: “алфавіт” (множина символів), “ланцюжок” (послідовність символів деякого алфавіту) і “мова” (множина ланцюжків у тому самому алфавіті).

1.1. Алфавіти

Алфавітом називають кінцева непуста множина символів. Домовимося позначати алфавіти символом ∑. Найбільше часто використаються наступні алфавіти.

1. = {0,1} — бінарний або двійковий алфавіт.

2. = {а, b, …, z} — множина малих літер англійського алфавіту.

3. Множина ASCII-символів або множина всіх друкованих ASCII-символів.

1.2. Ланцюжки

Ланцюжок, або іноді слово, — це кінцева послідовність символів деякого алфавіту. Наприклад, 01101 — це ланцюжок у бінарному алфавіті = {0, 1}. Ланцюжок 111 також є ланцюжком у цьому алфавіті.

Порожній ланцюжок

Порожній ланцюжок— це ланцюжок, що не містить жодного символу. Цей ланцюжок, позначуваний ε, можна розглядати як ланцюжок у будь-якому алфавіті.

Довжина ланцюжка

Часто виявляється зручним класифікувати ланцюжки по їхній довжині, тобто по числу позицій для символів у ланцюжку. Наприклад, ланцюжок 01101 має довжину 5. Звичайно говорять, що довжина ланцюжка — це “число символів” у ній. Це визначення широко поширене, але не цілком коректно. Так, у ланцюжку 01101 усього 2 символи, але число позицій у ній— п’ять, тому вона має довжину 5. Все-таки варто мати на увазі, що часто пишуть “число символів”, маючи на увазі “число позицій”.

Довжину деякого ланцюжка w звичайно позначають | w |. Наприклад, |011| = 3, a |ε| = 0.

Степеня алфавіту

Якщо — деякий алфавіт, то можна виразити множину всіх ланцюжків певної довжини, що складаються із символів даного алфавіту, використовуючи знак степеня. Визначимо k як множину всіх ланцюжків довжини k, що складаються із символів алфавіту .

Приклад 1. Помітимо, що ° = {ε} незалежно від алфавіту , тобто εєдиний ланцюжок довжини 0.

Якщо ={0, 1}, toді 1= {0, 1}, 2 = {00,01, 10, 11}, 3 = {000, 001, 010, 011, 100, 101, 110, 111} і так далі. Відзначимо, що між і 1 є невелике розходження. Справа в тому, що є алфавіт, і його елементи 0 і 1 є символами, а 1 є множиною ланцюжків, і його елементи — це ланцюжки 0 і 1, кожна довжиною 1. Ми не будемо вводити різні позначення для цих множин, думаючи, що з контексту буде зрозуміло, є {0, 1} або подібна йому множина алфавітом або ж множина ланцюжків.


Угоди про символи й ланцюжки

Як правило, малими літерами з початкової частини алфавіту (або цифрами) ми будемо позначати символи, а малими літерами з кінця алфавіту, наприклад w, х, в або z — ланцюжки. Керуючись цією угодою, ви легко зможете зрозуміти, елементи якого типу розглядаються в тому або іншому випадку.

Множина всіх ланцюжків над алфавітом прийнято позначати *. Так, наприклад,

{0,1}* = { ε, 0, 1,00,01, 10, 11,000, …}. По-іншому цю множину можна записати у вигляді


Іноді нам буде необхідно виключати з множину ланцюжків порожній ланцюжок. Множина всіх непустих ланцюжків в алфавіті позначають через +. Таким чином, мають місце наступні рівності:

+ = 1U2U3U…

*=+U{ε}.

Конкатенація ланцюжків

Нехай х и у — ланцюжки. Тоді ху позначає їхню конкатенацію (з’єднання), тобто ланцюжок, у якій послідовно записані ланцюжки х и у. Більш строго, якщо х — ланцюжок з i символів: х = а1, а2 .. аі, а у— ланцюжок з j символів: у = b1, b2 .. bj, то ху— це ланцюжок довжини i+j: ху = a1a2..alb1b2…bj

Приклад 2. Нехай х = 01101 й у=110. Тоді ху= 01101110, а ух= 11001101. Для будь-якого ланцюжка w справедливі рівності εw = wε
= w. Таким чином, ε
є одиницею (нейтральним елементом) щодо операції конкатенації, оскільки результат її конкатенації з будь-яким ланцюжком дає той же самий ланцюжок (аналогічно тому, як 0, нейтральний елемент щодо додавання, при додаванні з будь-яким числом х дає число х).

1.3. Мови

Множина ланцюжків, кожна з яких належить *, де — деякий фіксований алфавіт, називають мовою. Якщо — алфавіт, і L ∑* , то L — це мова над ∑, або в. Відзначимо, що мова в не обов’язково повинен містити ланцюжки, у які входять всі символи . Тому, якщо відомо, що L є мовою в , те можна затверджувати, що L — це мова над будь-яким алфавітом, що містить .

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Ijerarh Mov Za Homskim (519.5 KiB, Завантажень: 0)

Сторінка: 1 2 3 4 5 6 7 8 9 10
завантаження...
WordPress: 23.4MB | MySQL:26 | 0,613sec