Малюнок 2.7. Програма як діалектичне заперечення проблеми 5 страница

Визначення 4.8 Ланцюжок t є підланцюжком ланцюжка w, якщо w=utv для деяких ланцюжків u та v.

Нарешті, введемо поняття формальної мови.

Визначення 4.9 Якщо , то  називається формальною мовою (або просто мовою) над алфавітом  (в алфавіті ).

Приклад 4.6 Множина ланцюжків {aⁿbⁿcⁿ | n³0} = {e, abc, a²b²c², a³b³c³,…} є формальною мовою над алфавітом {a, b, c}.

Зауважимо, якщо L є мовою над Σ, то можна стверджувати, що L – це мова над будь-яким алфавітом Σ¢, що містить Σ. Іншими словами, є певна консервативність поняття мови до розширення алфавіту. Крім того, є монотонність множини мов відносно розширення алфавіту, бо це веде до збільшення множини мов. 

 

4.3 Операції над формальними мовами

Операції над формальними мовами розподіляються на два класи. Перший клас операцій відповідає над-абстрактній моделі мов, в якій вони мають інтенсіонал множини. Тому всі теоретико-множинні операції можна застосовувати для мов. В першу чергу, це операції об’єднання È, перетину È та різниці \. Вважаємо, що мови –аргументи цих операцій – задані над одним і тим самим алфавітом. Якщо це не так, то будуємо новий алфавіт, який є об’єднанням алфавітів мов-аргументів. Тоді всі мови-аргументи будуть мовами над одним алфавітом. Якщо мова L є мовою в алфавіті Σ, то мова Σ*–L називається доповненням мови L відносно алфавіту Σ. Коли з контексту ясно, про який алфавіт йде мова, говорять просто, що мова Σ*–L є доповненням мови L і позначається .

Приклад 4.7 Нехай L1={aⁿbⁿc^m| n,m ³0}, L2={aⁿb^mc^m| n,m ³0}. Тоді

L1ÇL2={ aⁿbⁿcⁿ| n³0}, L1\L2={ aⁿbⁿc^m| m¹n, n,m ³0}.

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

Визначення 4.10 Нехай . Тоді . Мова  називається конкатенацією мов  та .

Приклад 4.8 Якщо  та , то .

Найважливішою характеристикою операції добутку мов є її асоціативність. Одиницею цієї операції є мова, що складається з порожнього ланцюжка, тобто мова { e }. Похідною від добутку є операція піднесення до степені. Вважаємо, що  і.

Маючи степінь, дамо індуктивне визначення ітерації, яку ще називають замиканням Кліні, або «зірочкою Кліні».

Визначення 4.11 Ітерацією мови  (позначається ) називається мова .

Приклад 4.9 {ab}*={ e, ab, abab, ababab, …}.

Для мови, що складається з одного символа, фігурні дужки часто опускають і пишуть, наприклад, a* заміть (a}*.

Визначення 4.12 Оберненням або дзеркальним образом данцюжка  (позначається ) називається ланцюжок, складений із символів , взятих в оберненому порядку.

Приклад 4.10 Якщо , то .

Визначення 4.13 Нехай . Тоді .

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

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

За способом подання правильних ланцюжків формальні граматики поділяються на породжуючі і розпізнаючі (граматики породження та сприйняття). До породжуючих граматик відносяться граматики, які дозволяють побудувати будь-який правильний ланцюжок з зазначенням його структури і не дозволяють побудувати жодного неправильного ланцюжка. Розпізнаюча граматика – це граматика, яка дозволяє визначити, чи є довільно обраний ланцюжок правильним і, якщо він є правильним, визначити його структуру.

Формальні граматики широко застосовуються в лінгвістиці, інформатиці, логіці, та програмуванні у зв’язку з вивченням природних та штучних мов.

Почнемо з розгляду породжуючих граматик.

4.3 Породжуючі граматики

Як відзначалось на початку розділу, породжуючі граматики можуть розглядатися як конкретизації транзиційних систем або дедуктивних систем. Для таких систем головним є відношення переходів. В граматиках відношення переходу (виведення) задається за допомогою правил граматики (продукцій), які мають вигляд α→β, де α та β – ланцюжки в певному алфавіті S. Таке правило дозволяє перетворити ланцюжок γ₁ в ланцюжок γ₂ ( γ₁, γ₂ ÎS*) тоді і тільки тоді, коли γ₁ = δ₁αδ₂, γ₂ = δ₁βδ₂ для деяких ланцюжків δ₁ і δ₂, що належать S*. Змістовно, це правило дозволяє замінити підланцюжок γ₁, який співпадає з лівою частиною правила, на праву його частину, отримуючи ланцюжок γ₂.

Нехай P – множина продукцій. Тоді кожна продукція з P може розглядатися як правило виводу на S*. Сама послідовність правил, використаних в процесі породження деякого ланцюжка, є його виводом. Визначена таким способом граматика представляє собою формальну систему. Відомими прикладами формальних систем слугують логічні числення (числення висловлювань, числення предикатів), які детально вивчаються у відповідних розділах математичної логіки. Низку формальних систем для програм буде наведено в цьому посібнику.

Наведені міркування приводять до наступного визначення.

Визначення 4.14 Породжуючою граматикою (граматикою типу 0) називається четвірка G=(N, T, P, S), де N і T – скінчені алфавіти, NÇT=Ø, ,  скінчена і . Тут

·  – нетермінальний алфавіт (допоміжний алфавіт), його елементи називаються нетермінальними символами, нетерміналами, змінними,

· T – термінальний алфавіт (основний алфавіт), його елементи називаються термінальними символами або терміналами,

·  - початковий символ (аксіома).

·  – множина продукцій. Продукцію  інколи називають правилом підстановки, правилом виводу, або просто правилом і записують у вигляді .

Зробимо декілька зауважень до наведеного визначення. По-перше, слід пам’ятати про те, що вказана четвірка є просто екстенсіональним (одиничним) об’єктом поняття породжуваючої граматики і без посилань на інтенсіональні властивості граматик вона не є самодостатньою. Оскільки для нас важливою є єдність екстенсіональних та інтенсіональних аспектів, то ми вважаємо, що і у визначенні граматики така єдність повинна бути відзначена. По-друге, умова, що ліва частина правил належить множині  означає, що в лівій частині обов’язково повинен бути нетермінал. Це обмеження фактично індукується інтенсіональною ознакою породження, бо воно не повинно вестися із завершеного (термінального) ланцюжка. Разом з тим, в лівій частині можуть фігурувати і термінальні символи, які можуть замінюватись на символи правої частини правила. Це дозволяє говорити, що визначення породжуючої граматики не достатньо підтримує розподіл символів на термінальні та нетермінальні. Як вже відзначалось, від такого часткового рішення можна відмовитись, розглядаючи системи Туе (де нема розподілу на термінальні та нетермінальні символи), або розглядаючи контекстні граматики (де дозволена заміна лише нетермінального символа, але в певному контесті). По-третє, множини  були визначені як скінченні. Тим не менше, більшість результатів, що стосуються породжуючих граматик, може бути перенесена на нескінчені множини.

У прикладах нетермінальні символи зазвичай позначаємо великими літерами, термінальні – маленькими, для правил з однаковими лівими частинами  часто будемо використовувати скорочений запис . Крім того, у прикладах інколи будемо задавати граматику не як відповідну четвірку, а просто списком правил, вважаючи, що алфавіт N складають всі великі літери, які зустрічаються в правилах, а алфавіт T – всі маленькі літери, що зустрічаються в правилах. При цьому ліва частина першого правила є початковий символ .

Повторемо ще раз визначення відношення безпосередньої вивідності, яке задає граматика G=(N, T, P, S).

Визначення 4. 15 Нехай задано граматику G=(N, T, P, S). Пишемо γ₁Þ_Gγ₂ (γ₁, γ₂ Î ), якщо γ₁ = δ₁αδ₂, γ₂ = δ₁βδ₂  для деяких слів δ ₁, δ₂ Î , і .

Коли з контексту зрозуміло, про яку граматику йде мова, замість Þ_G можна писати просто Þ.

Визначення 4.16 Рефлексивне транзитивне замикання відношення безпосередньої вивідності називається відношенням вивідності і позначається через Þ*_G (або  _G).

Нагадуємо, що рефлексивним транзитивним замиканням бінарного відношення R на множині S є найменше відношення R¢, яке містить R, і яке є рефлексивним та транзитивним, тобто

1) sR¢s для всіх s з S;

2) якщо s₁Rs₂ та s₂R¢s₃, то s₁R¢s₃.

Наведене визначення не вказує на спосіб побудови рефлексивного транзитивного замикання. Разом з тим, з властивостей рефлексивного транзитивного замикання випливає, що ланцюжок γ_n виводиться з ланцюжка γ₀ (γ₀ *_Gγ_n) тоді і тільки тоді, коли деяка послідовність (можливо порожня) замін лівих частин продукцій з P їхніми правими частинами переводить ланцюжок γ₀ в γ_n. Іншими словами, коли існує послідовність виду γ₀Þ_G γ₁Þ_G... Þ_G γ_n ( ).

Визначення 4.17 Послідовність ланцюжків γ₀,γ₁,...γ_n, така, що γ_i-1Þ_Gγ_i для 1≤i≤n, називається виводом (виведенням) γ_n з γ₀ в G. Число  називається довжиною (кількістю кроків) цього виведення.

Зауважимо, що для довільного ланцюжка γ має місце γ Þ*_G γ (адже можливе виведення довжини 0). Слід також сказати, що вивід γ₀,γ₁,...γ_n не дає однозначного опису, які саме правила граматики були застосовані і до яких підланцюжків. Якщо така інформація є важливою, то можна застосовувати розмічений вивід, вказуючи входження лівої частини правила, що замінюється, та позначення правила, що було застосовано.

Визначення 4.18 Ланцюжки, що виводяться з певного нетерміналу A, називаються його словоформами (A-словоформами), або його сентенційними формами. Якщо вивід іде із аксіоми, то говоримо просто – словоформа, або сентенційна форма.

Приклад 4. 11 Для граматики з правилами { S ® aBSc, S ® e, B ® e} та аксіомою S словоформами будуть ланцюжкі aBSc, aBaBaBSccc, aaaBccc, та інші, які виводяться з S. 

Центральним є визначення, яке задає мову, що породжується граматикою.

Визначення 4.19 Мова, що породжується граматикою , – це множина ланцюжків L(G)={w | S *_Gw, wÎT*}. Будемо також говорити, що граматика  породжує мову .

Неформально кажучи, мова  є мовою, що породжується граматикою , якщо вона складається із ланцюжків (слів) в термінальному алфавіті, які виводяться із аксіоми S.

Інтенсіональні аспекти цього визначення були обговорені раніше. Зауважимо, що в попередньому підрозділі для побудови моделей формальних мов використовувся підхід від загального (абстрактного) до конкретного (одиничного). Спочатку вводилось поняття мови як множини речень, а в кінці побудов вводилось поняття породжуючої граматики. Це був інтенсіональний аналіз поняття граматики. В цьому підрозділи зроблено навпаки – ідуть екстенсіональні побудови: від екстенсіонального визначення породжуючої граматики через поняття виводу та його абстракції, і завешується поняттям мови, що породжується граматикою. Тут фактично можна говорити про визначення знизу-вверх: від індивідуальних донять – до загальних.

Ці міркування говорять про те, що поняття породжуючої граматики треба розглядати як єдність екстенсіоналу, що визначається четвірками вигляду G=(N, T, P, S) з вказаними раніше параметрами, та інтенсіоналу, що дає загальне визначення відношення безпосередньої вивідності Þ, його рефлексивного транзитивого замикання Þ*, та визначення мови, що породжується, за формулою L(G)={w | S *_Gw, wÎT*}.

 

Розглянемо на прикладі основні визначення та методи доведення властивостей граматик та породжуваних мов.

Нехай задана граматика G3=({S,B}, {a,b,c}, P, S), де

P={

P1: S ® aBSc,

P2: S ® e,

P3: Ba ® aB,

P4: Bb ® bB,

P5: Bc ® bc

  }      

Тут P1, P2, P3, P4, P5 – мітки відповідних правил.

Щоб зрозуміти, яку мову породжує ця граматика, побудуємо декілька виводів. Будемо використовувати розмічені виводи. Маємо:

1. S e.

---

Дата добавления: 2019-02-13; просмотров: 246; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!