У загальному випадку мова є безліч, а нескінченні об'єкти навіть задати важко: їх неможливо задати простим перерахуванням елементів. Будь-який кінцевий механізм завдання мови називається граматикою.
Формальна мова являє собою безліч ланцюжків у деякому кінцевому алфавіті. До формальних мов можна віднести штучні мови для спілкування людини з машиною – мови програмування.
Для завдання опису формальної мови необхідно, по-перше, вказати алфавіт, тобто сукупність об'єктів, званих символами (або літерами), кожен з яких можна відтворювати в необмеженій кількості екземплярів (подібно до звичайних друкованих літер або цифр), і, по-друге, задати формальну граматику мови, тобто перерахувати правила, за якими із символів будуються їх послідовності, що належать визначеній мові, – правильні ланцюжки.
Правила формальної граматики можна розглядати як продукції (правила виводу), тобто елементарні операції, які, будучи застосовані в певній послідовності до вихідного ланцюжка (аксіоми), породжують лише правильні ланцюжки. Сама послідовність правил, використаних у процесі народження деякого ланцюжка, є його висновком. Визначена таким чином мова є формальною системою.
За способом завдання правильних ланцюжків формальні граматики поділяються на які розпізнають. До тих, хто породжує відносяться граматики мови L,
за якими можна побудувати будь-який «правильний» ланцюжок із зазначенням його структури і не можна побудувати жодного неправильного ланцюжка. Розпізнаюча граматика мови L – це граматика, яка дозволяє встановити, чи правильний довільно обраний ланцюжок і, якщо він правильний, то з'ясувати його будову. Розпізнаюча грам-матика задає критерій приналежності довільного ланцюжка даної мови.
Формальні граматики широко застосовуються в лінгвістиці та програміро-
ванні у зв'язку з вивченням природних мов та мов програмування.
Автоматні та лінгвістичні моделі будуються на основі теорії формальних граматик, основи якої були закладені в роботах М. Хомського. Основними об'єктами, з якими має справу ця теорія, є символи, які є базовими елементами будь-якої непустої множини А будь-якої природи, а також ланцюжка, побудовані з цих елементів. Безліч А називають також абеткою.
Символи будемо позначати малими літерами латинського алфавіту, а ланцюжки – у вигляді ffghhh, які вважатимемо орієнтованими зліва направо. Ланцюжки позначатимемо також спеціальними символами – великими літерами латинського алфавіту або грецькими літерами, наприклад: = ffg, В = аbbа. Введемо в розгляд порожній ланцюжок , який не містить жодного символу.
Довжиною ланцюжка будемо називати число символів, що входять до цього ланцюжка.
Довжина ланцюжка позначається так:
| | = | ffg | = 3;
| У | = | аbbа | = 4;
Конкатенацією двох ланцюжків Х і Y називається такий ланцюжок Z, який отримує безпосереднє злиття ланцюжка Х, що стоїть зліва, і ланцюжок Y, що стоїть праворуч. Наприклад, якщо X = ffg, Y = ghh, то конкатенація Х та Y – це ланцюжок Z = ffgghh. Позначимо операцію конкатенації символом о. Властивості цієї операції
можна записати так:
1) властивість замкнутості:
про: А* × А* → А*;
2) властивість асоціативності:
(∀Х ∈ А*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
де через А* позначено безліч усіх можливих ланцюжків (зрозуміло, нескінченне), складених з кінцевої множини А базових елементів (символів) словника, включаючи порожній ланцюжок ; символ х позначає операцію декартового вироблення двох множин; а X, Y, Z – довільні ланцюжки, що належать А*.
Розглянемо пару (А*, 0). З урахуванням перерахованих властивостей операції ця пара являє собою напівгрупу з одиничним елементом або моноід. Напівгрупою в алгебрі називають лише безліч (у даному випадку А*), забезпечену скрізь певною асоціативною операцією.
Ланцюжок може належати або не належати мові L. Будь-яка множина ланцюжків L ≤ А* (де А* – моноід) називається формальною мовою, якщо ця множина ланцюжків визначена на алфавіті А.
Приклад 1. Нехай А – множина букв російського алфавіту. Тоді безліч ланцюжків, складених з п'яти букв, є формальною мовою L1. Інший приклад мови, визначеної на тому ж алфавіті - безліч L2 п'ятилітерних
слів російської, які можна розшукати в орфографічному словнику. Оче-
видно L2 ⊂ L1, оскільки багато ланцюжків мови L1 є російськими словами.
Нехай В і С - деякі підмножини множини А *.
Добутком множин В і С називається безліч D ланцюжків, являю-
ших конкатенацією ланцюжків з і З, тобто.
D = ( X o Y | X ∈ B, Y ∈ C).
Позначається твір в такий спосіб: D = ВC.
Розглянемо алфавіт А. Позначимо множину, що складається з , через А0. Визна-
ділимо ступінь алфавіту як Аn = An-1 A для кожного n1.
Неважко показати, що безліч усіх можливих ланцюжків алфавіту
Таку множину називають ітерацією алфавіту А. Усіченою ітерацією ал-
фавіту А називають
Якщо X і Y – ланцюжки множини А*, то ланцюжок Х називають підчіпкою це-
нирки Y, коли існують такі ланцюжки U та V з А*, що
При цьому, якщо U - порожній ланцюжок, то підчіпочку Х називають головою ланцюжок-
ки Y, а якщо V – порожній ланцюжок, то Х називають хвостом ланцюжка Y.
Конкатенація двох ланцюжків X та Y позначається ХоY або XY. Розглянемо пари ланцюжків (P1, Q1), (P2, Q2), ..., (Pn, Qn) з А * х А *. Співвідношеннями Туе називатимемо правила, згідно з якими будь-який ці-
нирці X = U Pi V з множини А * буде ставитися у відповідність ланцюжок Y = U Qi V, з тієї ж множини А * (i = 1, 2, ..., n) і навпаки. Ці співвідношення призводять до так званих асоціативних обчислень.
Якщо ланцюжок Y виходить із ланцюжка Х одноразовим застосуванням одного співвідношення Туе (тобто заміною підчіпки Pi на підчіпку Qi), говоритимемо, що Х та Y є суміжними ланцюжками.
Ланцюжок Хn співвідносний з ланцюжком Х0, якщо існує послідовність ланцюжків
Х0, Х1, ..., Хn,
така, що Х i-1 та Х i є суміжними ланцюжками.
Приклад 2. Нехай А - безліч букв російського алфавіту, на якому визна-
лім співвідношення Туе, яке полягає у праві заміни будь-якої однієї літери слова на будь-яку іншу. Тоді в послідовності ланцюжків МУКА, МУЗА, ЛУЗА, ЛОЗА, ПОЗА, ПОРА, ПОРТ, ТОРТ, два будь-які сусідні ланцюжки є суміжними, а ланцюжки МУКА і ТОРТ є співвідносними у сенсі заданих співвідношень.
Введення співвідношень Туе дозволяє виділити серед багатьох мов певні їх класи, які використовуються при побудові автоматно-лінгвістичних моделей різного типу.
Співвідношення Туе є двосторонніми, якщо ланцюжок Х є суміжним по відношенню до ланцюжка Y, і навпаки, ланцюжок Y є суміжним по відношенню до
ланцюжку Х. Більш цікавими, з точки зору теорії формальних граматик, є
ються співвідношення, у яких введено напрямок.
У цьому випадку їх називають напівспіввідношеннями Туе або продукціями та об-
означають так:
(Р1 → Q1), (P2 → Q2), ..., (Pn → Qn).
У тому випадку, коли є набір продукцій, кажуть, що ланцюжок Y непо-
засобів породжується з ланцюжка Х, і позначається як Х ⇒ Y, якщо існують такі ланцюжки U і V, що
X = U Pi V, Y = U Qi V,
а (Рi → Qi) – продукція з набору.
Говорять також, що Х породжує Y.
Якщо існує послідовність ланцюжків Х0, Х1, ..., Хn така, що для кож-
дого i = 1, 2, ..., n
Х i-1 ⇒ X i ,
то кажуть, що Хn породжується з Х0 (Х0 породжує Хn) і позначають як Х0 ⇒ * Xn. .
Граматики Хомського відповідають формальним комбінаторним схемам,
є напівсистемами Туе, в основу яких покладено півспіввідношення Туе
Анотація: У розділі розглядаються основи дисципліни: " формальна граматика " . Ця дисципліна розглядає будь-які операції із символами, а її висновки широко використовуються при аналізі формальних та "людських" мов, а також у штучному інтелекті. Ця лекція є найважливішою і одночасно найскладнішою для розуміння лекцією курсу. У зв'язку з цим автор подає читачеві лише її висновки, опускаючи математичні докази. Для кращого розуміння матеріалу може знадобитися звернення до матеріалів попередніх та наступних лекцій.
10.1. Алфавіт
Вивчення будь-якої мови людина починає з абетки. У формальної граматикимова визначається незалежно від його змісту. Більше того, одна і та ж мова може формуватися кількома граматиками! Це як у школі – не такий важливий результат (який можна прочитати наприкінці підручника), як його отримання – зафіксоване у зошит рішення завдання. Тому підійдемо до визначення алфавіту також формально.
П о д о р о д е н н ня. Алфавіт - це непуста кінцева безліч елементів.
У "класичному" мові алфавіт - це набір літер. У фонетиці - набір звуків мови, що видаються людиною. У музиці - це набір нот і т.д.
За допомогою алфавіту часто можна описати нескінченна безлічслів. Сукупність всіх слів, яку можна створити за допомогою граматики (іншими словами, що породжуються граматикою), називається мовою. На відміну від алфавіту, мова може бути нескінченною.
Будь-яка кінцева послідовність символів алфавітуназивається словом, або, професійніше, ланцюжком. Ланцюжками, що складаються із символів (a, b, c), будуть такі послідовності: a, b, c, aa, ab, bc, ac, bb, abba та інші. Також допускається існування порожнього ланцюжка Л – повна відсутність символів. Важливим є також порядок прямування символів у ланцюжку. Так, ланцюжки ab і ba – різні ланцюжки. Далі великі латинські літери будуть використані як змінні та символи, а малі латинські літери позначатимуть ланцюжки. Наприклад:
X = SVT Лістинг 10.1.
ланцюжок, що складається із символів S, V і T, і саме в цьому порядку.
П о д о р о д е н н ня. Довжиною ланцюжка називається число символів у цьому ланцюжку. Вона позначається як | x | . Наприклад: |Л| = 0, | = 1, | BA | = 2, | ABBA | = 4.
Якщо x і y є ланцюжками, їх конкатенацією буде ланцюжок xy . Від перестановки ланцюжків при конкатенації результат змінюється (як і теорії груп). Якщо z = xy – ланцюжок, то x – голова, а y – хвіст ланцюжка. Якщо нам байдужа голова ланцюжка, ми позначатимемо:
Z = … x Лістинг 10.2.
а якщо нам байдужий хвіст, ми писатимемо:
Z = x … Лістинг 10.3.
Про розподілення. Добуток двох множин ланцюжків визначається як конкатенація всіх ланцюжків, що входять до цих множин. Наприклад, якщо безліч A = (a, b), а B = (c, d) , то:
AB = (ac, ad, bc, bd) Лістинг 10.4.
У творі множин, як і за конкатенації, порядок множників істотний.
І при конкатенації ланцюжків, і при перемноженні множин ланцюжків істинним залишається асоціативний закон, що записується як:
Z = (ab) c = a (bc) = abc Лістинг 10.5.
D = (AB) C = A (BC) = ABC Лістинг 10.6.
І, нарешті, визначимо ступінь ланцюжка. Якщо x - непустий ланцюжок, то x 0 = (Л), x 1 = x, x 2 = xx, x n = x (x) (n-1). Те ж саме і зі ступенем множин.
10.2. Термінальні та нетермінальні символи
Поняття термінальних та нетермінальних символівтісно пов'язані з поняттям правила підстановки (чи продукції). Дамо його визначення.
П о д о р о д е н н ня. Продукцією, або правилом підстановки, називається впорядкована пара (U, x), що записується як:
U::= x Лістинг 10.7.
де U – символ, а x – непуста кінцева ланцюжок символів.
Символи, що зустрічаються лише у правій частині, називаються термінальними символами. Символи, що трапляються і в лівій, і в правій частині правил, називаються нетермінальними символами, або синтаксичними одиницями мови. Безліч нетермінальних символівпозначається як VN, а термінальних символів- VT.
Примітка. Дане визначення термінальних та нетермінальних символівістинно для КС-граматик та A-граматик (див. розділ 10.4.3).
П о д о р о д е н н ня. Граматикою G[Z] називають кінцеву, непусту безліч правил, що містить нетермінальний символ Z хоча б один раз на безлічі правил. Символ Z називають початковим символом. Далі ми всі нетермінальні символибудемо позначати як<символ>.
[Приклад 01]
Граматика: "число"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
Дамо ще визначення:
П о д о р о д е н н ня. Ланцюжок v безпосередньо породжує ланцюжок w , якщо:
V = x y, а w = xuy Лістинг 10.8.
де ::= u - правило граматики. Це позначається як v => w. Ми також говоримо, що ланцюжок w безпосередньо виводиться з v . При цьому ланцюжки x та y можуть бути порожніми.
П о д о р о д е н н ня. Кажуть, що v породжує w, або w приводиться до v, якщо існує кінцевий ланцюжок висновків u0, u1, …, u[n] (n > 0), такий, що
V = u0 => u1 => u2 => … => u[n] = w Лістинг 10.9.
Ця послідовність називається висновком довжиною n і позначається v => + w . І, нарешті, пишуть:
V =>* w, якщо v => w чи v =>+ w Лістинг 10.10.
10.3. Фрази
П о д о р о д е н н ня. Нехай G[Z] - граматика, x - ланцюжок. Тоді x називають сентенційною формою, якщо
П о д о р о д е н н ня. Нехай G[Z] - граматика. І нехай w = xuy – сентенційна форма. Тоді u називається фразою сентенціальної форми w для нетермінального символу , якщо:
Z =>* x y та => + u Лістинг 10.11.
Z =>* x y та => u Лістинг 10.12.
то ланцюжок u називається простою фразою.
Слід бути обережним із терміном "фраза". Той факт, що =>+ u (ланцюжок u виводиться з ) зовсім не означає, що u є фразою сентенційної форми x y; необхідна також виведення ланцюжка x y із початкового символу граматики Z .
Як ілюстрацію фрази розглянемо [Приклад 01] сентенційну форму<чс>1 . Чи означає це, що символ<чс>є фразою, якщо існує правило:<число> ::= <чс>? Звичайно ж, ні, оскільки неможливе виведення ланцюжка:<число><1>- З початкового символу:<число>. Які ж фрази сентенційної форми<чс>1? Розглянемо висновок:
<число> => <чс> => <чс><цифра> => <чс><1>Лістинг 10.13.
Таким чином,
<число> =>* <чс>і<чс> =>+ <чс>1 Лістинг 10.14.
Розглянемо формальну граматику, яка певною мірою нагадує фрагмент граматики російської мови та задає формальну мову, що складається з чотирьох російських речень. У цій формальній граматиці використовуються елементи, що відіграють роль членів речення або частин мови:
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
Ці елементи укладені в кутові дужки, щоб відрізняти їх від слів із фактичного словника, що становлять речення мови. У прикладі словник складається з наступних п'яти слів, чи «символів»: V= (будинок, дуб, заступає, старий, (точка)). Граматика має певні правила, що містять інформацію про те, як їх цих символів можна будувати пропозиції мови. Одне з цих правил таке:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
Це правило інтерпретується наступним чином: «Пропозиція може складатися з того, що підлягає, за яким слідує присудок, потім доповнення і точка». У граматиці цілком можуть бути інші правила, що задають пропозиції іншої структури. Однак у цій граматиці таких правил немає. Інші правила такі:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое>® заступає
5. <прилагательное>® старий
6. <существительное>® будинок
7. <существительное>® дуб
Застосуємо цю граматику породження (чи виведення) пропозиції.
За правилом 1 пропозиція має вигляд:
<предложение>1 ®<підлягаєе><сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><доповнення> 3 →
3 →<прикметнике><существительное> <сказуемое> <прилагательное> <существительное> 4 →Старий <существительное> <сказуемое> <прикметнике><существительное>
4 →Старий <существительное > <сказуемое> старий <существительное >
6,7 →Старий будинок <сказуемое> старий дуб
4 → Старий будинок затуляє старий дуб
Таким чином, отримуємо готову пропозицію:
Старий будинок заступає старий дуб.
Цей висновок можна зобразити у вигляді дерева. Дерево виведення показує, які правила застосовувалися до різних проміжних елементів, але приховує порядок застосування. Таким чином, можна бачити, що результуючий ланцюжок не залежить від порядку, в якому робилися заміни проміжних елементів. Кажуть, що дерево є «синтаксичну структуру»пропозиції.
Ідея висновку показує інші інтерпретації правил, подібних до правила <подлежащее> ® <прилагательное> <существительное> . Замість того, щоб говорити « підлягаєце прикметник, за яким слідує іменник», можна сказати, що підлягає"породжує" (або "з нього виводяться", або "його можна замінити на")<прикметник><существительное>.
За допомогою наведеної вище граматики можна вивести також три інші пропозиції, а саме:
Старий дуб заступає старий будинок.
Старий будинок заступає старий будинок.
Старий дуб заступає старий дуб.
Ці пропозиції та пропозиція, виведена раніше, і є всі пропозиції, що породжуються даною граматикою.
Безліч, що складається з цих чотирьох речень, називається мовою, яка визначається даною граматикою («породжується нею» або «виводиться в ній»).
Однією з формальних систем є система підстановок або напівсистема Туе (на ім'я норверзького математика Акселя Туе), яка визначається алфавітом А і кінцевою множиною підстановок виду:
де α i ,β i – слова, можливо і порожні в А, Þ – символ підстановки, який раніше ми розуміємо як «тягне», «виводиться».
У системі Туе використовуються відносини виду:
зрозумілі як пари підстановок:
α i Þ β i (ліва);
β i Üα i (права).
У напівсистемі Туе підстановка α i i i інтерпретується як правило виведення R i . Використовуючи ці напівсистеми, американський математик М. Хомський у 50-ті роки сформував і розвинув теорію про формальних граматик, що є їх окремим випадком.
Нехай V - непуста безліч символів - алфавіт (або словник) і, тим самим, задано безліч V * всіх кінцевих слів в алфавіті V. Формальна мова L в алфавіті V - це довільне підмножина V *. Так, якщо V містить літери російської мови, розділові знаки, символи прогалин і т.д., то V * - гіпотетичне безліч, що включає всі твори великої російської літератури (написані і майбутні).
Як символи можуть також використовуватися слова, математичні знаки, геометричні образи тощо.
Мови задаються чи визначаються граматикою- Системою правил, що породжують всі ланцюжки даного мови, і тільки їх.
Формальна граматика – формальна система, літочислення.
Розрізняють, що розпізнають, що породжують та перетворюють формальні граматики.
розпізнає, якщо для будь-якої ланцюжка, що розглядається, вона вирішує, чи є цей ланцюжок правильним у сенсі даної граматики.
Формальна граматика називається породжує, якщо може побудувати будь-який правильний ланцюжок.
Формальна граматика називається перетворюючою,якщо для будь-якого правильно побудованого ланцюжка вона будує її відображення у вигляді правильного ланцюжка.
Розглянемо клас формальних граматик, що породжують.
Формальною граматикою G, що породжує, називають четвірку
G=
де Т – кінцева непорожня множина кінцевих термінальних (основних) символів;
N – кінцева непорожня множина нетермінальних (допоміжних) символів;
Р - кінцева непорожня безліч правил виведення (продукцій);
S – початковий символ.
Т – термінальний словник – набір вихідних символів, у тому числі будуються ланцюжка, породжувані граматикою;
N – нетермінальний словник – набір допоміжних знаків, які означають класи вихідних знаків.
Кінцева множина – є повний словник граматики G.
Правило виведення – кінцева непорожня безліч двомісних відносин виду φÞψ, де φ і ψ – ланцюжки у словнику V, символ Þ – «замінити на».
Ланцюжок β безпосередньо виводиться з ланцюжка α в граматиці G (позначення αβ; індекс G опускається, якщо зрозуміло, про яку граматику йдеться), якщо α=α 1 φα 2 , β=α 1 ψα 2 , (φÞψ).
Ланцюжок β виводиться з α, якщо існує послідовність Е 0 =α, Е 1 ,Е 2 ,…,Е n =β, така, що " i =0,1,...,n-1 Е i =>Е i +1.
Ця послідовність називається виведенням β з α, а n – довжиною виведення.
Виведення β з α позначається α=> n β (якщо потрібно вказати довжину виведення).
Мовою L(G), що породжується граматикою G, називається безліч ланцюжків у термінальному словнику T, що виводяться з S, де S - початковий символ, що позначає клас мовних об'єктів, для яких призначена граматика. Початковий символ називають метою граматики чи її аксіомою.
Граматики G та G 1 еквівалентні, якщо L(G)=L(G 1).
При описі природної мови в термінах теорії формальних граматик термінальні символи інтерпретуються як слова або морфеми – найдрібніші осмислені одиниці мови (коріння, суфікси тощо), нетермінальні символи – як назви класів слів та словосполучень (підлягає, присудок та група оповіді .п.). Ланцюжок символів зазвичай інтерпретується як речення природної мови.
Приклад 1. Нехай граматика задана таким чином:
T-(a,b), N-(S,A,B), S-S,
P=(1. SÞaB; 2.SÞbA; 3. AÞaS; 4. AÞbAA; 5. AÞa; 6.BÞbS; 7. BÞaBB; 8. BÞb).
Типові висновки пропозицій:
У дужках над стрілками вказаний номер правила виведення. Висновок закінчується, т.к. немає правила P з лівою частиною, що дорівнює ab.
Граф такої граматики, що породжує, зображений на рис. 125.
Мал. 125. Граф граматики, що породжує.
Тут a та b – кінцеві вершини (термінальні).
Приклад 2. Нехай граматика задана таким чином:
Т=(<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};
N=(<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};
Можна вивести ланцюжок<прилежный> <студент> <выполняет> <домашнее задание>.
Очевидно, що останній ланцюжок виведення є заключним і є пропозицією природної мови. Аналогічно можна вивести ланцюжок<ленивый> <студент> <не выполняет> <домашнее задание>. Зауважимо, що у цьому прикладі нетермінальними символами є синтаксичні категорії.
Висновок можна описати так званим структурним деревом, зображеним на рис. 126.
Мал. 126. Структурне дерево виведення речення
Граматика може задаватися і так званими синтаксичними діаграмами Вірта – як у мові Паскаль, які нагадують перемикальні схеми, в яких послідовне з'єднання вказує ланцюжок, а паралельне – варіанти ланцюжків – замість символу.
Отже, формальні граматики можуть бути такими, що розпізнають, породжують, перетворюють. Крім того, теоретично формальних граматик розрізняють чотири типи мов, що породжуються чотирма типами граматик. Граматики виділяють шляхом положення обмежень, що послідовно посилюються, на систему правил Р.
Загальноприйнятою класифікацією граматик та народжуваних ними мов є ієрархія Хомського, що містить чотири типи граматик.
Граматика типу 0– це граматика, в якій не накладається жодних обмежень на правила виведення jÞy, де j та y можуть бути будь-якими ланцюжками з V. Така граматика може бути реалізована машиною Тьюринга. У цьому стан машини Тьюринга відповідають нетермінальним (допоміжним) символам, а символи на стрічці – термінальним. Правила породження ланцюжків описуються системою команд.
Граматика типу 1 – це граматика, всі правила якої мають вигляд aAbÞawb, де wÎTUN, А – нетермінальний символ. Ланцюжки a та b – контекст правил. Вони не змінюються під час його застосування. Таким чином, у граматиках типу 1 окремий термінальний символ А переходить у непустий ланцюжок w (А можна замінити на w) тільки в контексті a та b. Граматики типу 1 називають контекстними чи контекстно-залежними.
Граматика типу 2– це граматика, у якій допустимі лише правила виду АÞa, де aÎТUN, тобто. a – непустий ланцюжок з V. Граматики типу 2 називають безконтекстними чи контекстно-вільними. Сучасні алгоритмічні мови описуються за допомогою контекстно-вільних граматик.
Граматика типу 3 – мають правила виду А?aB, або A?b, де А,В?N; a,bÎT.
Тут A, B, a, b – одиночні символи (не ланцюжка) відповідних словників. Мови, які задаються граматиками цього типу, називаються автоматними чи регулярними.
При цьому використовується мова регулярних виразів (регулярна мова):
Така мова задається кінцевим автоматом (теорема Кліні). У більшості алгоритмічних мов вирази задаються кінцевими автоматами або регулярними виразами.
Розглянемо приклад завдання кінцевим автоматом регулярної мови:
X = (0,1) - безліч вхідних символів;
Y=(S,A,B,q k ) – безліч внутрішніх станів, q k – кінцевий стан, S – початковий стан.
Іноді розглядають кілька кінцевих станів і об'єднують їх у безліч F. У цьому випадку F = (q k).
j: функція переходів – недетермінована:
Граф переходів кінцевого недетермінованого автомата показано на рис. 127.
Мал. 127. Граф переходів кінцевого недетермінованого автомата
Відповідна граматика, що породжує, має вигляд:
Відповідна регулярна мова L= 
:
0, 010, 01010,...
Теорія формальних граматик використовується при побудові компіляторів. Компілятор проводить аналіз вихідної програми. У цьому визначається, чи є задана ланцюжок символів правильно побудованою пропозицією, і, якщо це, то відновлюється її вид. Розбір чи синтаксичний аналіз виконується спеціальною програмою – парсером (to parse – розбирати). Для вирішення цього завдання розроблено спеціальні програми, наприклад, LEX та YACC.
В операційній системі UNIX є стандартні програми LEX та GREP – вони побудовані на основі теорії регулярних мов.
Програма LEX-здійснює лексичний аналіз тексту – розбивку тексту відповідно до певного набору регулярних виразів.
Програма GREP – виділяє зразок за регулярним виразом – тобто. проводить контекстний пошук у одному чи кількох файлах, у своїй будується кінцевий автомат, який подаються символи з вхідного потоку символів.
У системах автоматичного перекладу з однієї мови іншою виявляються підлягає, присудок, визначення, доповнення; Потім складається відповідне речення щодо правил необхідної мови.
В даний час в комп'ютерах використовуються перекладачі типу Promt, Magic Gooddy, Socrat Personal. Крім того, використовуються і прості словники, типу Context, Socrat Dictionary, МультиЛекс.
Подання за допомогою формальних граматик лінгвістичних знань є однією з моделей представлення знань взагалі, що використовуються в такій галузі, як системи з елементами штучного інтелекту. Слід зазначити, що знання відрізняються від даних, наприклад тим, що дані змістовно інтерпретуються лише відповідною програмою ЕОМ, а в знаннях можливість змістовної інтерпретації завжди присутня . Програмно-апаратна частина систем, що забезпечують інтерфейс з користувачем природною або близькою до природної мови, реалізується лінгвістичним процесором, Завдання якого – прямий і зворотний переклад природно-мовних текстів на формальну мову внутрішнього уявлення, з яким працює ЕОМ.
У Японії деякі фірми вже почали продаж побутових «розмовляючих» роботів, які можуть спілкуватися з господарем.
У лінгвістичному процесорі виділяють декларативну та процедуральну частини. Перша містить опис словників, друга – алгоритм аналізу та синтезу природно-мовних текстів.
Логічними моделями представлення знань є вже відомі нам обчислення висловлювань та предикатів.
Основою формалізації семантичних (смислових) знань про деяку предметну область є звані семантичні мережі . Семантична мережа – орієнтований граф, вершинам якого ставляться у відповідність конкретні об'єкти, а дугам – семантичні відносини з-поміж них. Мітки вершин мають посилальний характер і є деякими іменами. У ролі імен можуть виступати, наприклад, слова природної мови. Мітки дуг позначають елементи множини відносин. Крім того, для представлення знань використовуються кадри, які найчастіше визначають як структуру даних для представлення стереотипних ситуацій.
Теореми Геделя
У математичної логіці доводиться, що літочислення предикатів несуперечливе – тобто. в ньому неможливо одночасно вивести, і. Крім того, через теорему Геделя про повноту обчислення предикатів загальнозначуща формула виводиться в обчисленні предикатів.
Розглянуте літочислення предикатів - літочислення предикатів першого порядку. У обчислення другого порядку можливі квантори по предикатам, тобто. вирази виду "Р(Р(х)), або за функціями.
Отже, безліч всіх справжніх висловлювань логіки висловлювань перераховано та розв'язно. Безліч всіх істинних висловлювань логіки предикатів перелічимо (через його повноти), але нерозв'язно (через нескінченність предметної області).
Як ще одну формальну теорію в математичній логіці розглядається так звана формальна арифметика, запропонована італійським математиком Джузеппе Пеано (1858-1932 рр.). Пеано ввів символи та операції Î, U, I та вперше викладав логіку як математичну дисципліну. Вперше спробу зведення математики до логіки було здійснено німецьким математиком і логіком Готтлібом Фреге (1848-1925 рр.). Це він визначив безліч як обсяг поняття. Він писав: «Арифметика є частиною логіки і має запозичувати ні в досвіду, ні в споглядання жодних основ доказів». Знаменитий парадокс про безліч усіх множин – це протиріччя у системі Фреге, виявлене Бертраном Расселом.
Гёдель довів, що будь-яка формальна теорія Т, що містить формальну арифметику, неповна: у ній існує замкнута формула F, така, що істинно, але ні F, ні не виведені в Т. Відповідно до знаменитої теореми Геделя про неповноту, для будь-якої несуперечливої формальної теорії Т, що містить формальну арифметику, формула, що виражає несуперечність Т, недоведена Т.
Таким чином, арифметика і теорія чисел є теоріями, що не аксиматизуються, а безліч усіх справжніх висловлювань арифметики неперелічимо.
Теореми Геделя мають важливе методологічне значення. Виявляється, для досить багатих математичних теорій немає адекватних формалізацій. Щоправда, будь-яку неповну теорію Т можна розширити, додавши до неї як аксіоми істинну, але не виведену в Т формулу, проте, нова теорія також буде неповна. З іншого боку, неможливо досліджувати метавластивості теорії засобами самої формальної теорії, тобто. всяка метатеорія Т для того, щоб мати можливість доводити хоча б несуперечність, повинна бути багатшою за Т .
Таким чином, під сумнів береться сам підхід побудови математики як деякої фіксованої сукупності коштів, які можна було б оголосити єдино законними та з їхньою допомогою будувати метатеорії будь-яких теорій. Але це не крах формального підходу. Наявність нерозв'язних проблем не говорить про те, що конструктивний підхід не придатний, якщо він чогось і не може, лише тому, що цього не може ніхто.
Неможливість повної формалізації змістовно певних теорій – це недолік концепції, а об'єктивний факт, непереборний ніякої концепцією.
Неможливість адекватної формалізації теорії означає, що треба або шукати її фрагменти, що формуються, або будувати сильнішу формальну теорію, яка, щоправда, знову буде неповна, але, можливо, буде містити всю вихідну теорію.
НЕКЛАСІЧНІ ЛОГІКИ
ВВЕДЕНИЕ………… ………………………………….…………….4
Глава 1. МОВИ І ГРАМАТИКИ. ПОЗНАЧЕННЯ, ВИЗНАЧЕННЯ І КЛАСИФІКАЦІЯ………………………………………………………………………………6
1.1. Концепція граматики мови. Позначення……………………………………………7
1.2. Класифікація граматик за Хомським………………………..…………………13
1.3. Техніка побудови КС-і А-граматик…………………………………………..16
1.4. Синтаксичні дерева виведення у КС-граматиках. Подання
А-граматик як графа станів. Неоднозначність граматик……………..19
1.5. Синтаксичний аналіз А-языков…………………………………………………..23
Вправи……………………………………………………………………………….29
Глава 2. РОЗІЗНАВАЧІ ТА АВТОМАТИ.……………………………….….…………32
Глава 3. АВТОМАТНІ ГРАМАТИКИ І КІНЦЕВІ АВТОМАТИ…………….35
3.1. Автоматні граматики та кінцеві автомати…………………………………….35
3.2.Еквівалентність недетермінованих та детермінованих А-граматик…… 36
Вправи………………………………………………………………………………… 41
Глава 4. ЕКВІВАЛЕНТНІ ПЕРЕТВОРЕННЯ КОНТЕКСТНО-ВІЛЬНИХ
І АВТОМАТНИХ ГРАМАТИК………………………………………………..….42
4.2. Виняток тупикових правил з граматик………………………………………46
4.3. Узагальнені КС-граматики та приведення граматик до подовжувальної форми…….48
4.4. Усунення лівої рекурсії і ліва факторизация………………………………..…52
Вправи………………………………………………………………………………….53
Глава 5. ВЛАСТИВОСТІ АВТОМАТНИХ І КОНТЕКСТНО-ВІЛЬНИХ МОВ…55
5.1. Загальний вид ланцюжків А-мов і КС-мов………………………………………..55
5.2. Операції над мовами………………………………………………………………….59
5.2.1. Операції над КС-мовами………………………………………………………59
5.2.2. Операції над А-языками………………………………………………………62
5.2.3. Операції над К-мовами………………………………………………………66
5.3. Висновки для практики…………….………………………………………………….67
5.4. Неоднозначність КС-граматик та мов…………………………………………71
Вправи…………………………………………………………………………....…74
Глава 6. СИНТАКСИЧНИЙ АНАЛІЗ КС-мов……………………………...……...75
6.1. Методи аналізу КС-мов. Граматики попередження………………….…75
6.2. Граматики попередження Вірта……………………………………………...77
Граматики попередження Флойда…….……………………………………...79
Функції попередження…………………………………………………………81
Вправи………………………………………………………………………………84
Глава 7. ВСТУП У СЕМАНТИКУ……………………………………………………….85
7.1. Польський інверсний запис….……………………………………………………...85
7.2. Інтерпретація ПОЛІЗу……………………………….………………………..….87
7.3. Генерування команд з ПОЛІЗу………………………………….…………....89
7.4. Алгоритм Замельсона і Бауера перекладу виразів у ПОЛІЗ………..……….91
7.5. Атрибутні граматики……………………………………………………………97
Вправи……………………………………………………………………………..100
Глава 8. ОСНОВНІ ФАЗИ КОМПІЛЯЦІЇ……………………………………...……100
ВИСНОВОК
ДОДАТОК…………………………………………………………………………………105
ПРЕДМЕТНИЙ ПОКАЗНИК……………………………………………………….…….…115
Вступ
Лінгвістика- Наука про мову. Математична лінгвістика- наука, що займається формальними методами побудови та вивчення мов.
Теорія формальних граматик- Розділ математичної лінгвістики, що включає способи опису формальних граматик мов, побудова методів та алгоритмів аналізу належності ланцюжків мови, а також алгоритмів перекладу (трансляції) алгоритмічних мов на мову машини.
Імпульсом до створення та вдосконалення цієї теорії послужило розвиток обчислювальної техніки і, як наслідок, необхідність у засобах спілкування людини з ЕОМ. У всіх застосуваннях ЕОМ повинна розуміти будь-яку мову, якою користувач може повідомити їй алгоритми вирішення завдань і вихідні дані. Кожна ЕОМ має власну мову машинних команд, що подаються в двійковому коді і відображають окремі операції процесора. На перших етапах розвитку обчислювальної техніки програмісти спілкувалися з ЕОМ саме цією примітивною мовою, але людина не здатна добре мислити в категоріях цифрової мови машини. Автоматизація програмування призвела до створення спочатку мов асемблера, а потім і алгоритмічних мов високого рівня, переклад з яких рідною машинною мовою було доручено самій ЕОМ. Програми такого перекладу називаються трансляторами.
З проблемами пояснення мови машині стикаються багато розробників програмного забезпечення. Людині властиво винаходити нові мови. Тут може йтися не лише про складні компілятори для нових алгоритмічних мов програмування. Будь-яка автоматизована система повинна розуміти деяку вхідну мову запитів. Нові інформаційні технології передбачають залучення кінцевого користувача (вченого, конструктора, технолога, оператора) - спеціаліста у конкретній галузі, а чи не у сфері обчислювальної техніки та технології програмування, до вирішення своїх завдань на ЕОМ. Для якісного вирішення цієї проблеми між користувачем та ЕОМ повинен існувати інтелектуальний інтерфейс: користувач повинен ставити завдання та отримувати результати їх вирішення у термінах відомої йому предметної області. Тобто, потрібна розробка широкого спектра предметно-орієнтованих мов. Спеціаліст у галузі програмного забезпечення повинен знати, як створюються мови та їх програмна підтримка.
Щоб пояснити мову машині, необхідно чітко уявляти, як вона влаштована і як ми її розуміємо. Замислившись над цим, ми побачимо, що не знаємо, як ми розуміємо нашу рідну мову. Процес цього розуміння підсвідомий, інтуїтивний. Але щоб створити транслятор, необхідно мати алгоритм перекладу тексту на ті дії, які цей текст вимагає виконати, а це, у свою чергу, вимагає формалізації мови. Завдання формалізації мови та вирішує математична лінгвістика. Природні мови надто складні, і формалізувати їх повністю поки що не вдається. Алгоритмічні мови, навпаки, вже створюються у розрахунку формалізацію. Теорія формальних мов - це найбільш розвинена галузь математичної лінгвістики, що представляє насправді методику пояснення мови машині. Перш ніж розглядати визначення, моделі та методи цієї теорії, розглянемо деякі поняття на прикладах із природних мов.
Мова- Це безліч пропозицій (фраз), побудованих за певними правилами.
Граматика- Зведення правил, визначальних належність фрази мови.
Будь-яка мова має задовольняти властивості розв'язності та однозначності.
Мова дозволимоякщо за кінцевий час можна визначити, що фраза або речення належить мові. Мова однозначнаякщо будь-яка фраза розуміється єдиним чином.
Основними розділами граматики є синтаксис та семантика.
Синтаксис- Зведення правил, визначальних правильність побудови речень мови.
Семантика- зведення правил, визначальних семантичну чи смислову правильність речень мови.
Пропозиція може бути синтаксично вірною та семантично невірною.
Синтаксис зазвичай спрощується тим, що не фрази мови повинні мати сенс. Найчастіше важко зрозуміти сенс футуристів або деяких політиків. У зв'язку з цим цікавий приклад академіка Л.В.Щерби: «Глоча куздра штеко бушнула бокра і кучерить бокренка». Це фраза російською, оскільки її можна розібрати по членам пропозиції, але зміст її неясен.
Синтаксичний аналіз фрази можна записати як дерева граматичного розбору. Вузли дерева, такі як підлягає, присудок, група підлягає, речення відповідає синтаксичним поняттям, а листя – це слова, з яких будується пропозиція. Обрубавши в дереві частину листя і гілок, ми отримаємо сентенційну форму (ланцюжок, що виводиться).
<предложение>
Природу неоднозначності фрази можна пояснити на прикладі того ж дерева розбору для фрази «Мати любить дочку».
Ця фраза двозначна, оскільки має два варіанти синтаксичного аналізу. Синтаксична неоднозначність безпосередньо тягне за собою неоднозначність семантичну. Але можна запропонувати і приклади синтаксично однозначних фраз, які можуть бути не зрозумілі через неоднозначне значення слів. Нагадаємо, що алгоритмічна мова має бути однозначною.
Формальна мова – це математична абстракція, що виникла як узагальнення традиційних лінгвістичних понять природних мов. Теорія формальних мов вивчає переважно синтаксис мов і є фундаментом синтаксично керованих процесів перекладу, якого можна віднести трансляцію, асемблювання і компіляцію. Основи цієї теорії були закладені американським математиком Н. Хомським наприкінці 50-х на початку 60-х років і до теперішнього часу продовжують розвиватися разом з розвитком обчислювальної техніки. Зупинимося на основних елементах цієї теорії.