формальні мови граматики та автомати

формальні мови граматики та автомати

Не дивлячись на свою простоту, модель скінченного автомата виявилася надзвичайно зручною у застосуванні не тільки в інформатиці, але і в багатьох інших галузях інженерної діяльності. Разом з класичними додатками теорії автоматів, такими як проектування вбудованих систем логічного управління, обробка текстів і побудова компіляторів штучних мов, останнім часом з явилися нові, нетрадиційні області застосування цієї теорії - специфікація і верифікація систем взаємодіючих процесів (зокрема, протоколів комунікації), мови опису документів і об єктно - орієнтованих програмних систем, оптимізація логічних програм та інші. Послідовні пристрої виробляють вихідні сигнали, залежні не тільки від вхідних сигналів, що поступають в даний момент, але і від передісторії раніше, тобто від вхідних сигналів, що поступають раніше, для зберігання передісторії ці пристрої володіють пам яттю, а отже їх називають схемами з пам яттю. Скінченний автомат - в теорії алгоритмів математична абстракція, що дозволяє описувати шляхи зміни стану об єкту залежно від його поточного стану і вхідних даних, за умови, що загальна можлива кількість станів кінцева. Кінцеві автомати широко використовуються на практиці, наприклад в синтаксичних, лексичних аналізаторах, і тестуванні програмного забезпечення на основі моделей. У кожен такт дискретного часу на вхід автомата надходить чергова буква оброблюваного слова, під її впливом автомат міняє свій стан; стан, у який автомат перейде, визначається попереднім його станом і прочитаною буквою вхідного слова. Діаграма являє собою орієнтований граф, вершини якого одноіменні станам автомата; дуга з вершини q i, у вершину q k з надписаною над нею буквою а j проводиться тоді й тільки тоді, коли g(q i, а j)=q k. Почавши роботу в стані q 0, автомат під впливом букв a, b із цього стану не виходить; під впливом букви с реалізується перехід у стан q 1; будь - яка далі вступна буква залишає автомат у тім же стані. L 2 - множина слів, у яких буква а зустрічається парне число разів; l 3 - множина слів, що починаються й закінчуються однаковою буквою; l 4 - множина слів, що містять підслово =abbc; l 5 - множина слів, при читанні яких з ліво на право різниця між числом зустрінутих букв a й b ніколи не перевершує 2. Так, наприклад, автомат k 5, обробивши деяку частину вхідного слова, виявляється в стані q гар, якщо в прочитаній їм частині вхідного слова число зустрінутих букв а перевищує число зустрінутих букв b на x; тут x; автомат виявляється в стані q пог, якщо в деякий момент роботи автомата абсолютна величина різниці між числом оброблених букв а й числом оброблених букв b перевищила 2. Можна вважати, що кожен автомат має не більше одного позитивно поглинаючого й не більше одного негативно поглинаючого стану (якщо позитивно або негативно поглинаючих станів декілька, то вони легко можуть бути замінені одним). Звичайно в діаграмі переходів негативно поглинаючий стан не зображується; якщо з деякого стану по деякій букві перехід не зазначений, то передбачається, що він веде в негативно поглинаючий стан. Нехай l (p) позначає множину слів - записів у десятковій системі числення всіх цілих ненегативних чисел, кратних натуральній константі p; будемо вважати, що мові l (p) додатково належить також порожнє слово. Станами автомата вважаємо q 0, q 1, q 2, q p - 1; з довільного стану q i по цифрі х, х, автомат переходить у стан q j, якщо залишок від поділу числа iх (тобто числа, одержуваного приписуванням до числа i цифри х праворуч) на p дорівнює j. Завдяки зазначеній структурі переходів автомат, що обробив, починаючи від початкового стану q 0, записане в десятковій системі числення ціле ненегативне число, виявляється в стані q y тоді й тільки тоді, коли залишок від розподілу на p дорівнює y. Представлений два стани, які має, скінченний автомат, що розпізнає числа, кратні п яти (використовується той факт, що кратне п яти число має своєю останньою цифрою 0 або 5). Відзначимо, що мова, розпізнавана довільним скінченним автоматом, містить порожнє слово тоді й тільки тоді, коли початкове стан цього автомата належить множині f. Проводимо з даної вершини n дуг, над першої надписуємо а 1, над другий - а 2, …, над n - ої - а n, кінцями цих дуг є n вершин наступного (у цьому випадку - першого) рівня. Виконавши розгалуження в кожній з вершин першого рівня, одержуємо n 2 вершин другого рівня; виконавши розгалуження в кожній з вершин другого рівня, одержуємо n 3 вершин третього рівня, і т. Операції розгалуження у вершинах r - го рівня не виконуються; якщо на вхід автомата, що перебуває в деякому стані з r - го рівня, надходить ще одна буква, він переходить у невідображене діаграмою негативно поглинаючий стан q п ог. Між вершинами - станами побудованого r - уровневого дерева й довжину не більше, ніж r, словами алфавіту а існує взаємно однозначна відповідність - кожному такому слову зіставляється стан, у якому виявляється автомат, що обробив, починаючи від q 0, дане слово. Сукупність g (q i, а j) - це завжди непуста підмножина станів автомата, у кожне з яких він може перейти зі стану q i під впливом букви а j, тут q i q, а j а. Детермінований скінченний автомат є окремим випадком недетермінованого, він виходить із останнього в припущенні, що всі множини g (q i, а j) є одноелементними.

Слово належить мові l (к) тоді й тільки тоді, коли є послідовність станів автомата така, що … при цьому іншими словами, слово (належить мові l (к) тоді й тільки тоді, коли існує спосіб роботи даного автомата над даним словом такий, що після завершення обробки (автомат виявляється в стані, що належить множині f. Приклад недетермінованого скінченного автомата к 1 (причина недетермінованості полягає в тім, що під впливом букви а автомат зі стану q 0 може або перейти в стан q 1, або залишитися в стані q 0). По довільному недетермінованому кінцевому автомату к = 0, g, f>, що розпізнає мову l (к), детермінований автомат к= 0, g, f> такий, що l (к)=l (к), будуємо в такий спосіб. Функцію переходів автомата к будуємо таким чином, щоб, обробивши з q 0 довільне слово, цей автомат приходив у стан, що представляє собою підмножина станів вихідного автомата к, у кожне з яких к може перейти зі свого початкового стану в результаті обробки деяким способом даного слова. Тому що слово належить l (k) тоді й тільки тоді, коли існує спосіб роботи автомата к над даним словом такий, що після завершення обробки автомат виявляється в одному зі станів множини f, сукупність f визначаємо в такий спосіб. Для недетермінованого скінченного автомата з n станами завжди можна побудувати еквівалентний йому детермінований скінченний автомат, що має 2 n - 1 стан. Зі станів сукупності 0, q 1 > по букві а автомат к переходить у стани тієї ж сукупності, а по букві b як зі стану q 0, так і зі стану q 1 реалізується перехід в q 2. інші мислимі стани - підмножини виявляються зайвими, вони недосяжні; почавши роботу зі свого початкового стану, автомат може виявлятися тільки в трьох уведених станах (включаючи початкове). По кожній букві х вхідного алфавіту а з q 0 проводимо дві дуги з надписаною буквою х; верхня дуга має своїм кінцем вершину g 1 (q 1 0, х), тобто стан, у яке переходить зі свого початкового стану під впливом букви х перший автомат, а нижня - вершину g 2 (q 2 0, х), тобто стан, у яке переходить зі свого початкового стану під впливом букви х другий автомат. На першому такті обробки будь - якого непустого вхідного слова =х автомат має можливість переходу з q 0 або по верхньої, або по нижній дузі з надписаною буквою х. Якщо реалізовано перехід по верхній дузі, то далі фактично працює автомат к 1 і перевіряється приналежність слова мові l 1; якщо реалізовано перехід по нижній дузі, далі працює автомат к 2 і перевіряється приналежність слова мові l 2; побудований автомат у результаті обробки довільного вхідного слова може виявитися в стані, що належить підмножині f, тоді й тільки тоді, коли належить об єднанню мов l 1 й l 2. Представлена діаграма переходів побудованого за викладеною схемою недетермінованого скінченного автомата, що розпізнає множину чисел, кожне з яких кратне 2 або 5. Задано ланцюжок, що складається з термінальних символів, і формальна граматика, потрібно визначити, чи належить заданий ланцюжок мові, що породжується заданою граматикою. Операцію заміни частини заданого ланцюжка, що збігає із правою частиною будь - якого правила, лівою частиною цього правила називають безпосереднім згортанням. істотно те, що для деяких класів контекстно - вільних граматик і для автоматних граматик цю процедуру вдається істотно спростити й, більше того, побудувати пристрої, що виконують процедуру розпізнавання автоматично. При вивченні формальних мов звичайно припускають, що слово, що подається на вхід розпізнавача, попередньо записується на нескінченну вхідну стрічку, обмежену з однієї сторони.

На практиці функцію переходів задають у вигляді двовимірної таблиці, що називають таблицею переходів розпізнавача, або у вигляді орієнтованого графа, який називають діаграмою переходів розпізнавача. У кожній клітині таблиці, що відповідає рядку, відзначеної станом s i, і стовпцю, відзначеному вхідним символом p k, записується стан s m, обумовлений функцією переходів ц (s i, p k) = s m. Щоб побудувати діаграму переходів розпізнавача, потрібно кожному стану зіставити вершину графа й позначити цю вершину символом стану, а кожному переходу, обумовленому функцією ц (s i, p k) = s m, дугу графа s m, відзначену вхідним символом p k і з єднуючої вершини s i, і s m. Якщо такту роботи відповідає конфігурація (s k, pб), де p - символ, розташований під читаючою головкою, і, якщо визначено функцію переходів ц(s k, p)=s i, те формується нова конфігурація (s i, б), що відповідає наступному такту роботи.

Вхідне слово (ланцюжок) б називається припустимим для розпізнавача а, якщо при послідовному читанні символів б с вхідної стрічки розпізнавач переходить із початкової конфігурації в одну з кінцевих конфігурацій. Щоб уникнути невизначеності через відсутність символу в правій частині правила, умовимося використовувати символ порожнього ланцюжка, записуючи таке правило у вигляді е $. Ланцюжки 1 і 2 залишаються незмінними при застосуванні правила, тому їх називають контекстом (відповідно лівим і правим), а граматику - контекстно - залежною. V t = a, b, c, d >, v a = i, a, b >, r = i aai (1) ai aai (2) aa aba (3) a b (4) bba bcda (5) bi ba > (6) є контекстно - залежною, оскільки друге і шосте правила мають непорожній лівий контекст, а третє і п яте правила містять обидва контексти.

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

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

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

(4) у загальному випадку, якщо описана множина ланцюжків, що являють собою деяку мову, і потрібно побудувати граматику, яка породжує цю множину ланцюжків, то слід робити так. Початком може бути кожна з букв (множину букв позначимо нетермінальним символом c), а основна частина (нетермінальний символ а) являє собою список без роздільників, елементами якого можуть бути або букви, або цифри (множину цифр позначимо нетермінальним символом d). Такі вирази являють собою ланцюжки, які можна розглядати як списки з роздільниками, в яких роль роздільників виконують знаки операцій (нетермінальний символ w). (5) щоб побудувати граматику, яка допускає використання в арифметичних виразах дужок без вкладеності, подамо структуру таких виразів у вигляді списку з роздільниками, елементами якого є вираз (нетермінальний симол h) без дужок, або вираз, узятий в дужки.

Як умову (нетермінальний символ r) в таких операторах дозволяється використовувати відносини, що складаються з ідентифікатора a та числа від одного до дев яти (нетермінальний символ d), з єднаних знаками.

Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере.

Нехай в деякий момент часу так знаходиться в стані sk і під впливом вхідного сигналу х, що поступає в цей момент, переходить в стан sl, виробляючи вихідний сигнал у, тоді процес переходу так з sk в sl можна записати.

При опрацюванні теоретичного матеріалу звернять увагу на те, що теорія формальних граматик та мов є основним розділом математичної лінгвістики – специфічної математичної дисципліни, орієнтованої на вивчення структури природних та штучних мов. Ця теорія виникла в 50 - х роках у працях американського лінгвіста ноама хемського, який виходив виключно з потреб лінгвістики, що традиційно розуміється як наука про побудову природної мови.

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

Формальна граматика називається розпізнавальною, якщо для будь - якого розглянутого ланцюжка вона вміє вирішити, чи є цей ланцюжок правильним чи ні, а у випадку позитивної відповіді дати вказівки про будову цього ланцюжка. Формальна граматика називається породжуючою, якщо вона вміє побудувати будь - який правильний ланцюжок, даючи при цьому вказівки про його будову, і не будує ні одного неправильного ланцюжка. Формальна граматика називається трансформаційною, якщо для будь - якого правильно побудованого ланцюжка вона вміє побудувати його відображення знову ж у вигляді правильного ланцюжка, задаючи при цьому вказівки про порядок проведення відображень. Термінальний словник – набір вихідних елементів, з яких будуються ланцюжки, що породжуються граматикою, або словник основних слів мови, з яких будуються речення. Домовимося при написанні конкретних граматик першими рядковими латинськими буквами а, b, с позначати елементи термінального словника; елементи нетермінального словника – прописними латинськими а, в, с, а елементи загального словника v – рядковими грецькими.

Граматика називається граматикою типу 2 – безконтекстною, якщо в системі правил р припустимі лише правила виду, де а - нетермінальний символ - непустий ланцюжок з v.