Обчислення. Формальні системи.
Формальні граматики. автомати
Існує клас задач, математичні моделі та алгоритми, рішення яких зручно представляти у вигляді формальних числень. Поряд з машиною станів і функціями, обчислюваних алгоритмом, «алгоритм-числення» є третім видом уточнення поняття алгоритму. Технологія проектування програм, заснована на формальних обчисленнях, володіє певною специфікою, яка і розглядається в цій лекції.
1. Обчислення і формальні системи
Змістовно обчислення задає конструктивний спосіб породження слів деякого мови. Наприклад, обчислення кінцевих різниць Ньютона дає можливість породжувати (обчислювати) для деякого правильного вираження формул з диференціалами все еквівалентні йому вирази, задані правилами тотожних перетворень. Обчислення висловлювань дозволяє конструктивно породжувати, всі можливі логічні закони у вигляді тотожно істинних висловлювань. Обчислення предикатів дозволяє будувати формальні теорії у вигляді системи формул, які істинні в обраній інтерпретації.
1.1. Обчислення ТУЕ (Норвезька математик ТУЕ в 1912 р сформулював найбільш загальну модель обчислення)
де - кінцевий алфавіт
- правила підстановок, де, (- слова з алфавіту А). А * - всі слова в алфавіті А; правила «працюють» в обидві сторони.
ІТ дозволяє конструктивно вирішити два основні завдання - завдання породження і завдання розпізнавання слів, що входять в ІТ.
а) Завдання породження еквівалентних слів в ІТ.
Задано слово, породити всі можливі слова W. виведені з Z по правилам Р з ІТ. Безліч слів, виведених з Z. називаються класом еквівалентності по Z. а все, такі, що з, називаються еквівалентними (W).
б) Завдання розпізнавання еквівалентності пари слів.
ZW (еквівалентні), якщо з Z виводиться слово W за правилами Р.
Порядок застосування правил при вирішенні завдань не регламентований і здійснюється відповідно до деревом повного перебору.
Приклад 1., де - порожня множина. Слово являє собою рядок Маркова.
Слово «аbа» в цьому ІТ виводиться декількома шляхами (послідовностями застосування правил).
1.2. Обчислення Ербрана - Геделя. (ІЕГ)
У 1934 р Ербран і не незалежно від нього Гедель як уточнення поняття алгоритму побудували формальне числення для обчислення всіх можливих функцій на множині натуральних чисел.
б) ППФ - правильно побудовані формули, які складаються з термів, побудованих за правилами, прийнятим в математиці, і мають вигляд -, де і - терми.
- підстановка знака цифри замість імені змінної
- заміна (підстановка) терма на цифру (число).
Приклад 2. Задана система ППФ.
Обчислити функцію при значеннях
Якщо визначити системою ППФ як операцію додавання
то за правилом.
Алгоритм у вигляді обчислення Ербрана - Геделя не визначає порядок застосування правил підстановок і не визначає навіть схему підстановок, як це прийнято в рекурсивних функціях Кліні. Як в і в будь-яких визначеннях поняття алгоритму (МТ, НАМ, РФ) формалізм ІЕГ побудований тільки на перетвореннях послідовності символів і не вимагає залучення ніякої семантики.
2. Формальні системи (ФС)
Формальна система суть числення, де виділено підмножина формул (слів), яке оголошено спочатку виведеним. Ці формули називаються аксіомами.
а) ППФ - правильно побудовані формули в алфавіті А,
б); А * - безліч слів побудоване в алфавіті А.
в) - аксіоми є підмножиною ППФ.
г) ПВ - правила виду, що означає, з сукупності ППФ виведена ППФ. У будь-ФС безліч формул ППФВ виводяться з ППФА за допомогою правил ПВ. При цьому ППФВ> ППФ>, - називаються виведеними формулами.
Наприклад, обчислення висловлювань є формальною системою, де ППФ є формули, побудовані з імен змінних, знаків операцій ( - кон'юнкція, - диз'юнкція, - заперечення, - імплікація) і дужок. Виділяються ППФ, які оголошуються аксіомами і єдине правило виведення «modus ponens». У численні висловів породжуються тільки такі ППФ. які можуть інтерпретуватися як тотожне справжні формули (тавтології) і тільки вони.
3. Формальні граматики (ФГ)
Обчислення у вигляді ФС запропоновано американським математиком Хомским (1953 р) спочатку для вирішення проблем структурної лінгвістики, а далі опису формальних мов програмування.
ФГ =. де А - термінальний алфавіт
- допоміжний алфавіт, S - єдина аксіома, Р - правила виду і, де.
ФГ породжує характерну мову у вигляді підмножини слів. Правила ФГ не містять ніяких обмежень на рекурсивность підстановок.
4. Автомати і граматики
а) Кінцевий алфавіт - термінальний алфавіт (малі латинські букви).
б) - все слова, отримані з букв алфавіту, - операція ітерації приписування (конкатенації). Наприклад слово = aabcc отримано з «а» приписуванням букви «а» до літери «а» - далі отримано послідовним приписуванням до слова букв.
в) - мова, взагалі кажучи, складається з нескінченного числа слів. Виникає проблема опису мови за допомогою кінцевих і конструктивних об'єктів (наприклад, формул або правил породження).
Як завжди, розглядаються дві основні задачі.
г) Породження язикаL. Для породження слова служить спеціальна конструкція - породжує граматика G. яка являє собою кінцевий набір продукцій (правил підстановок) для виведення будь-яких слів мови зі спеціального символу S (аксіоми) і тільки їх.
A - основний алфавіт, V - допоміжний алфавіт, - аксіома
- об'єднаний алфавіт,, Р - правила (підстановки, продукції): має вигляд, де (в загальному випадку) (слова в об'єднаному алфавіті)
д) Розпізнавання слів язикаL. Дано слово , визначити чи. Для вирішення цього завдання служать розпізнають автомати. Формально автомат визначається -, де А - основний алфавіт, S - алфавіт станів, Р - правила виду, si. wi Sj. ,
4.1. Автоматна (регулярна) граматика -AГ і
кінцевий автомат - КА.
Автоматна граматика, де А - основний алфавіт; Р - правила виду - аксіома. Кінцевий автомат, де А - основний алфавіт; S - алфавіт станів; s0 - початковий стан; sk - кінцевий стан; Р - правила виду
Приклад 3. Для мови L1 задані:
безлічстанів автомата
- маркер кінця слова
АГ правила порожденіяКА- правила переходу
АГ породжує слова мови L1 КА розпізнає слова мови L1.
Якщо задані правила АГ, то правила КА виходять формальними переносами символів A з правої частини правил в ліву (див. Приклад). Якщо задані правила КА, то правила АГ перенесенням символів A в праву частину правил.
КА задається графом переходів і по суті є машиною станів (SM).
Крім того, автоматний мову задається регулярним виразом (формулою з букв А, знаків операцій: «» - конкатенація, «» - ітерація, «» розділене «або»). Для прикладу 3 регулярний вираз для L1 = ().
Приклад 4. Нехай для мови L2 на малюнку заданий граф КА і слово, кажуть, що розпізнається КА, якщо перебуваючи в під дією потрапляє в Слова НЕ розпізнається КА; КА з S0 під дією w2 залишиться в S1. тому немає правила виводить з S1 під дією якого-небудь символу крім «b» і «».
Регулярний вираз для мови, слова якого розпізнаються КА.
Приклад 5. Висновок деякого слова в АГ з прикладу 3.
Висновок слова aaacbbb. У кружочках зазначено номери правил.
4.2. Теореми Кліні. (Пряма і зворотна)
а) За регулярним виразом може бути побудований КА
б) За КА може бути побудовано регулярний вираз
Формально будь-яка машина станів є кінцевим автоматом і тому на SM поширюється теорема Кліні.
5. Контекстно-вільні граматики та магазинні
автомати. Контекстно-вільні мови.
Існують мови, які не можуть бути описані регулярним виразом і відповідно не може бути побудований КА, який розпізнавав би слова цієї мови.
Приклад такої мови, де ... Кількість a і b в слові L3 однаково, наприклад, слово, а слово.
Контекстно-вільна граматика (КСГ).
A - алфавіт мови (термінальний алфавіт) =; V- допоміжний алфавіт =, де - початковий символ - аксіома ( «початок»); - об'єднаний алфавіт Р - правила виду, де, - слово з букв об'єднаного алфавіту.
Приклад 6. Породжуюча граматика для
Породжують правила (підстановки, продукції)
1. Висновок слова aaacbbb
На відміну від АГ граматики з прикладу 3, яка породжує слова і в тому числі, KCГ з прикладу 6 породжує слова з рівною кількістю «a» і «b» і тільки їх.
Мови, які породжуються КС - граматиками називаються контекстно-свободниміязикамі.
Схожі документи:
регулярні безлічі і вирази, кінцеві автомати. Лекція 12 Граматики і розпізнавачі Ланцюжки виведення. і R визначено в деякій формальнойсістеме. наприклад, в алгебрі величин, алгебри множин, в обчисленні висловлювань і т. п. наприклад.
Принцип логічного програмування. Формальні (аксіоматичні) системи. Поняття формальнойсістеми. формальний висновок. Обчислення висловлювань як формальнаясістема. Теорема дедукції.
лінгвістики, зокрема, так звані трансформаційні граматики. розроблені Н. Хомський. В даний. формальнимісістемамі. отриманими в результаті розвитку природничо-наукових дисциплін (такі диференціальне, інтегральне числення.
формальній логіці умовно і залежить від угоди? А ось і ні. Хоча всередині логіки обчислень. граматика працює не зі словом, а з лексикою. Між 1934 і! 93б роками В. в курсі лекцій. дівітельно, що автомати і фізіологічні системи можна охопити.
освіта: гімнастика, граматика. музика і. Його робота «Лекції по індустріальному. елементарних тверджень числення висловів ». даної формальнойсістеме. виводиться в іншій системі. більше. Створення виробничих автоматів. виконують основні.