Скінченні автомати

Размещено на http://www.allbest.ru/

Вступ

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

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

1. Загальна характеристика скінченних автоматів

1.1 Теорія скінченних автоматів

автомат недетермінований скінченний розпізнавач

Всі цифрові пристрої поділяються на два класи:

- Комбінаційні пристрої.

- Послідовні пристрої (автомати).

Комбінаційні пристрої виробляють вихідні сигнали, залежно від значень вхідних і не зв'язані з часом надходження вхідних сигналів. Один і той же вхідний сигнал перетворюється в один і той же вихідний сигнал, залежно від часу надходження.

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

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

Описом цих пристроїв займається теорія скінченних автоматів.

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

Існують різні варіанти завдання скінченного автомата. Наприклад, скінченний автомат може бути заданий за допомогою п'яти параметрів:

,

де Q - кінцева множина станів автомата;

q0 - початковий стан автомата ();

F - множина кінцевих (або допустимих) станів, таких що ;

У - допустимий вхідний алфавіт (кінцева множина допустимих вхідних символів), з якого формуються рядки, що прочитуються автоматом;

д - задане відображення множини в множину підмножини Q:

(іноді д називають функцією переходів автомата).

Автомат починає роботу в стані q0, прочитуючи по одному символу вхідного рядка. Лічений символ переводить автомат в новий стан із Q відповідно до функції переходів. Якщо після закінчення прочитування вхідного слова (ланцюжки символів) автомат опиняється в одному з допускаючих станів, то слово «приймається» автоматом. В цьому випадку говорять, що воно належить мові даного автомата. Інакше слово «відкидається».

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

1.2 Детермінований скінченний автомат

В кібернетиці автоматами називають технічно або програмно реалізовані модулі, призначені для переробки вступник інформації. Скінченний автомат - це модуль, що має кінцеве число можливих станів і функціонуючий у дискретному часі. Кінцеві автомати вивчаються як абстрактні алгоритмічні пристрої, призначені для обробки слів фіксованого вхідного алфавіту. Уважаємо, що обробку довільного слова у вхідному алфавіті А автомат починає зі спеціально виділеного початкового стану. У кожен такт дискретного часу на вхід автомата надходить чергова буква оброблюваного слова, під її впливом автомат міняє свій стан; стан, у який автомат перейде, визначається попереднім його станом і прочитаною буквою вхідного слова. Над словом довжини L автомат працює L тактів. Результат роботи автомата визначається станом, у якому він виявляється по її завершенні.

Формально скінченний автомат СА визначаємо як сукупність

К={Q, A, q₀, g, F},

де Q={q₀, q₁, q₂,…, q_m} - множина станів автомата; А={а₁, а₂,…, а_n} - вхідний алфавіт; q₀ - спеціально виділений стан автомата, іменований початковим станом; g - функція переходів скінченного автомата, що представляє собою відображення типу QxАQ (якщо g(q_i, а_j)=q_k, то автомат зі стану q_i під впливом букви а_j повинен перейти в стан q_k); F - спеціально виділена підмножина станів автомата, які ми умовно будемо йменувати «гарними», FQ.

Нехай вхідне слово, l()=р. Через q(t) позначимо стан, у якому виявляється автомат К через t тактів роботи над цим словом (тут t=0, 1, 2,…, р): q(0) =q₀.

Будемо вважати, що слово приймається автоматом К, якщо q(р) F. Введемо в розгляд мову L(К): слово належить мові L(К), якщо дане слово приймається автоматом К. Мова L(К) іменуємо мовою, розпізнаваною даним кінцевим автоматом. Мову L назвемо регулярною, якщо для неї можна побудувати скінченний автомат, що розпізнає.

Скінченний автомат зручно задавати діаграмою його переходів. Діаграма являє собою орієнтований граф, вершини якого одноіменні станам автомата; дуга з вершини q_i, у вершину q_k з надписаною над нею буквою а_j проводиться тоді й тільки тоді, коли g(q_i, а_j)=q_k. У випадку, коли перехід з q_i в q_k здійснюється під впливом кожної з букв деякої підмножини S, SА, всі букви цієї підмножини підписуються над відповідною дугою (замість переліку всіх букв допускається скорочений запис «xS» або просто «S»). Якщо довільний стан q_i входит в F, то даний факт на діаграмі відзначається жирним кружком, що виділяє вершину q_i.

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

Размещено на http://www.allbest.ru/

Рис. 1.1. - Діаграма автомата K₁

На рис. 1.1 показана діаграма автомата K₁, що працює над словами алфавіту A={a, b, c}. Автомат має два стани, q₀ й q₁, причому «гарним» є тільки стан q₁. Почавши роботу в стані q₀, автомат під впливом букв a, b із цього стану не виходить; під впливом букви с реалізується перехід у стан q₁; будь-яка далі вступна буква залишає автомат у тім же стані. Таким чином, автомат K₁ розпізнає мова L₁, що складається зі слів, що мають у своєму составі букву с. Дана мова є регулярною.

Приведемо ще кілька прикладів регулярних мов у тім же алфавіті: L₂ - множина слів, у яких буква а зустрічається парне число разів; L₃ - множина слів, що починаються й закінчуються однаковою буквою; L₄ - множина слів, що містять підслово =abbc; L₅ - множина слів, при читанні яких з ліво на право різниця між числом зустрінутих букв a й b ніколи не перевершує 2.



Размещено на http://www.allbest.ru/

Рис. 1.2. - Діаграма скінченного автомата K₂

Діаграми скінченних автоматів K₂ - K₅, що розпізнають мови L₂ - L₅ відповідно, представлені на рисунках 1.2 - 1.5. Інформацію про оброблену частину вхідного слова автомат «пам'ятає» своїм станом. Так, наприклад, автомат K₅, обробивши деяку частину вхідного слова, виявляється в стані q_гар, якщо в прочитаній їм частині вхідного слова число зустрінутих букв а перевищує число зустрінутих букв b на x; тут x{-2, -1, 0, 1, 2}; автомат виявляється в стані q_пог, якщо в деякий момент роботи автомата абсолютна величина різниці між числом оброблених букв а й числом оброблених букв b перевищила 2.

Стан скінченного автомата назвемо поглинаючим, якщо будь-яка вхідна буква не виводить автомат із цього стану. Поглинаючий стан назвемо позитивно поглинаючим, якщо він належить F, і негативно поглинаючим у противному випадку. В автоматах K₁ й K₄ позитивно поглинаючими є стани q₁ й q₄ відповідно, в автоматі K₅ негативно поглинаючим є стан q_пог.

Можна вважати, що кожен автомат має не більше одного позитивно поглинаючого й не більше одного негативно поглинаючого стану (якщо позитивно або негативно поглинаючих станів декілька, то вони легко можуть бути замінені одним). Звичайно в діаграмі переходів негативно поглинаючий стан не зображується; якщо з деякого стану по деякій букві перехід не зазначений, то передбачається, що він веде в негативно поглинаючий стан. Скінченний автомат розпізнає в алфавіті А мову, що складається зі слів, у які буква с входить рівно один раз. Цей автомат має 3 стани, негативно поглинаючий стан q_пог(у нього автомат переходить зі стану q₁ по букві с) у діаграмі не зазначено.

Уведемо алфавіт B={0, 1, 2, …, 9}, кожне слово в цьому алфавіті трактуємо як ціле ненегативне число. Нехай L^(p) позначає множину слів - записів у десятковій системі числення всіх цілих ненегативних чисел, кратних натуральній константі p; будемо вважати, що мові L^(p) додатково належить також порожнє слово . Покажемо, що L^(p) - регулярна мова. Що розпізнає L^(p) скінченний автомат К^(p) можна побудувати в такий спосіб. Станами автомата вважаємо q₀, q₁, q₂, q_p-1; з довільного стану q_i по цифрі х, х{0, 1, 2,…, 9}, автомат переходить у стан q_j, якщо залишок від поділу числа iх (тобто числа, одержуваного приписуванням до числа i цифри х праворуч) на p дорівнює j. Завдяки зазначеній структурі переходів автомат, що обробив, починаючи від початкового стану q₀, записане в десятковій системі числення ціле ненегативне число , виявляється в стані q_y тоді й тільки тоді, коли залишок від розподілу на p дорівнює y. Єдиним «гарним» станом автомата K^(p) варто вважати q₀.

Відзначимо, що в ряді випадків, виходячи з інших принципів, можна побудувати розпізнающу подільність на p автомати c меншим числом станів. Представлений два стани, які має, скінченний автомат, що розпізнає числа, кратні п'яти (використовується той факт, що кратне п'яти число має своєю останньою цифрою 0 або 5).

По кінцевому автомату К^(p) легко будується автомат К^(p)[], що розпізнає мову L^(p)\{}. Для одержання діаграми переходів автомата К^(p)[] у наявній діаграмі переходів автомата К^(p) робляться наступні зміни: початковий стан q₀ автомата К^(p) перейменовуємо в q₀; уводимо новий початковий стан q₀; по довільній цифрі х з q₀ автомат К^(p)[] реалізує перехід у той же стан, що й автомат К^(p) зі свого початкового стану (при цьому замість переходу в q₀ завжди реалізується перехід в q₀); єдиним «гарним» станом автомата К^(p)[] варто вважати q₀. Відповідно, початковий стан автомата К^(p)[] є безповоротним - у процесі обробки будь-якого вхідного слова, вийшовши із цього стану, автомат у нього ніколи не повернеться.

Відзначимо, що мова, розпізнавана довільним скінченним автоматом, містить порожнє слово тоді й тільки тоді, коли початкове стан цього автомата належить множині F.

Порожня мова, універсальна мова, будь-яка кінцева мова в довільному фіксованому алфавіті А={а₁, а₂,…, а_n} є регулярною мовою.

Кожен скінченний автомат з порожньою множиною «гарних» станів F розпізнає порожню мову. Кожен скінченний автомат, у якому кожен стан «гарний», розпізнає універсальну мову.

Зараз припустимо, що мова L кінцева, нехай L={₁, ₂,…, _p}. Діаграму скінченного автомата К(L), що розпізнає слова мови L, будуємо у вигляді дерева, коренем якого є вершина q₀, що утворить нульовий рівень. У вершині q₀ реалізуємо розгалуження (далі ця операція буде виконуватися й для інших вершин): проводимо з даної вершини n дуг, над першої надписуємо а₁, над другий - а₂,…, над n-ої - а_n, кінцями цих дуг є n вершин наступного (у цьому випадку - першого) рівня. Виконавши розгалуження в кожній з вершин першого рівня, одержуємо n² вершин другого рівня; виконавши розгалуження в кожній з вершин другого рівня, одержуємо n³ вершин третього рівня, і т.д. Процес триває доти, поки не будуть побудовані вершини r-го рівня, де r - число букв у самому довгому слові мови L. Операції розгалуження у вершинах r-го рівня не виконуються; якщо на вхід автомата, що перебуває в деякому стані з r-го рівня, надходить ще одна буква, він переходить у невідображене діаграмою негативно поглинаючий стан q_пог. Між вершинами-станами побудованого r-уровневого дерева й довжину не більше, ніж r, словами алфавіту А існує взаємно однозначна відповідність - кожному такому слову зіставляється стан, у якому виявляється автомат, що обробив, починаючи від q₀, дане слово. Кожне відображене в дереві станів автомата К(L) називаємо ім'ям відповідного йому слова (стан q₀ одержує при цьому ім'я порожнього слова). Множина F «гарних» станів автомата К(L) уважаємо наступної: ₁, ₂,… _p. Побудова скінченного автомата що розпізнає мову L закінчено. Теорема доведена повністю.

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

1.3 Недетермінований скінченний автомат

Недетермінований скінченний автомат визначаємо як сукупність К*={Q, A, q₀, g*, F}, де Q, A, q₀ й F мають той же зміст, що в п. 1.2, а функція переходів g* є відображенням типу QxА[2^Q\]. Нагадаємо, що для будь-якої множини М через 2^М позначається множина всіх підмножин з М; символ позначає порожню множину. Сукупність g*(q_i, а_j) - це завжди непуста підмножина станів автомата, у кожне з яких він може перейти зі стану q_i під впливом букви а_j, тут q_iQ, а_jА.

На відміну від недетермінованих автоматів, кінцеві автомати, уведені в попередньому пункті, іменовані детермінованими. Детермінований скінченний автомат є окремим випадком недетермінованого, він виходить із останнього в припущенні, що всі множини g*(q_i, а_j) є одноелементними.

Будучи запущений у роботу над довільним словом зі свого початкового стану, недетермінований скінченний автомат може функціонувати по-різному. Мова L (К*), розпізнаваний недетермінованим кінцевим автоматом К*, визначаємо в такий спосіб: слово належить мові L (К*) тоді й тільки тоді, коли є послідовність станів автомата така, що … при цьому іншими словами, слово (належить мові L (К*) тоді й тільки тоді, коли існує спосіб роботи даного автомата над даним словом такий, що після завершення обробки (автомат виявляється в стані, що належить множині F.

Приклад недетермінованого скінченного автомата К₁* (причина недетермінованості полягає в тім, що під впливом букви а автомат зі стану q₀ може або перейти в стан q₁, або залишитися в стані q₀). Легко бачити, що мова L(К₁*) збігається з раніше уведеною регулярною мовою L₄.

Размещено на http://www.allbest.ru/

Недетермінований скінченний автомат К₁

Мови, обумовлені недетермінованими скінченними автоматами, є регулярними мовами.

По довільному недетермінованому кінцевому автомату К*={Q, A, q₀, g*, F}, що розпізнає мову L (К*), детермінований автомат К={Q, A, q₀, g, F} такий, що L (К)=L (К*), будуємо в такий спосіб. Думаємо Q=2^Q\, тобто станами автомата К уважаємо непусті підмножини станів автомата К*, при цьому визначаємо q₀={q₀}. Функцію переходів автомата К будуємо таким чином, щоб, обробивши з q₀ довільне слово , цей автомат приходив у стан, що представляє собою підмножина станів вихідного автомата К*, у кожне з яких К* може перейти зі свого початкового стану в результаті обробки деяким способом даного слова . Досягнення зазначеної мети забезпечується наступним визначенням функції g:

q_ug(q_i, a_j) (q_vq_i) таке, що {q_ug*(q_v, а_j)}.



Тому що слово належить L (K*) тоді й тільки тоді, коли існує спосіб роботи автомата К* над даним словом такий, що після завершення обробки автомат виявляється в одному зі станів множини F, сукупність F визначаємо в такий спосіб: довільний стан q_iF тоді й тільки тоді, коли q_iF.

Побудований викладеним способом детермінований скінченний автомат розпізнає та ж мова, що й вихідний автомат К*.

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

Два автомати називаємо еквівалентними, якщо вони розпізнають одну і ту саму мову. Для недетермінованого скінченного автомата з N станами завжди можна побудувати еквівалентний йому детермінований скінченний автомат, що має 2^N-1 стан. У дійсності число необхідних станів може виявитися меншим. На рис. 1.15. представлений недетермінований автомат К*, що має 3 стани. Діаграму переходів еквівалентного йому детермінований скінченного автомата К будуємо в такий спосіб. Уводимо вершину - стан {q₀}. Зі свого початкового стану q₀ автомат К^* по букві а або переходить в q₁, або залишається в q₀; по букві b автомат переходить в q₂. Тому автомат К по букві а з {q₀} переходить у стан {q₀, q₁}, а по букві b переходить у стан {q₂}. Зі станів сукупності {q₀, q₁} по букві а автомат К* переходить у стани тієї ж сукупності, а по букві b як зі стану q₀, так і зі стану q₁ реалізується перехід в q₂. Тому автомат К по букві а з {q₀, q₁} переходить у той же стан {q₀, q₁}, а по букві b переходить у стан {q₂}. Зі стану q₂ автомат К* по букві а переходить в q₀, а по букві b - залишається в q₂. Тому автомат К по букві а з {q₂} переходить в {q₀}, а по букві b - залишається в {q₂}. Побудова автомата К закінчена. Інші мислимі стани-підмножини виявляються зайвими, вони недосяжні; почавши роботу зі свого початкового стану, автомат може виявлятися тільки в трьох уведених станах (включаючи початкове).



Размещено на http://www.allbest.ru/

Недетермінований автомат К* та детермінований скінченний автомата К

Концепція недетермінованого скінченного автомата легко застосовується для побудови автомата, що розпізнає об'єднання двох регулярних мов. Нехай L₁ й L₂ - регулярні мови, розпізнавані кінцевими автоматами К¹={Q¹, A, q¹₀, g¹, F¹} і К²={Q², A, q²₀, g², F²} відповідно. Нехай D₁ й D₂ - діаграми переходів, що визначають ці кінцеві автомати. Для побудови діаграми переходів D автомата, що розпізнає об'єднання мов L₁ й L₂, поєднуємо ці діаграми в такий спосіб. Уводимо нову вершину - стан q₀. По кожній букві х вхідного алфавіту А з q₀ проводимо дві дуги з надписаною буквою х; верхня дуга має своїм кінцем вершину g¹(q¹₀, х), тобто стан, у яке переходить зі свого початкового стану під впливом букви х перший автомат, а нижня - вершину g²(q²₀, х), тобто стан, у яке переходить зі свого початкового стану під впливом букви х другий автомат. Початковим станом побудованого автомата вважаємо q₀; множину F його «гарних» станів визначаємо як об'єднання множин F¹ й F². Спеціально відзначимо, що у випадку, коли хоча б в одному з автоматів К¹, К² початковий стан є «гарним», в F варто включити стан q₀. На першому такті обробки будь-якого непустого вхідного слова =х автомат має можливість переходу з q₀ або по верхньої, або по нижній дузі з надписаною буквою х. Якщо реалізовано перехід по верхній дузі, то далі фактично працює автомат К¹ і перевіряється приналежність слова мові L₁; якщо реалізовано перехід по нижній дузі, далі працює автомат К² і перевіряється приналежність слова мові L₂; побудований автомат у результаті обробки довільного вхідного слова може виявитися в стані, що належить підмножині F, тоді й тільки тоді, коли належить об'єднанню мов L₁ й L₂. Представлена діаграма переходів побудованого за викладеною схемою недетермінованого скінченного автомата, що розпізнає множину чисел, кожне з яких кратне 2 або 5.

Размещено на http://www.allbest.ru/

Діаграма переходів недетермінованого скінченного автомата, що розпізнає множину чисел, кожне з яких кратне 2 або 5

1.4 Автоматні граматики та розпізнавачі

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

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

Допустимо, що задано граматику, схема якої має вигляд:

R = {<I>> a <B> x, B > b <B>, <B>> y},

і ланцюжок символів abyx. Виконавши операцію згортання за допомогою третього правила, одержимо ланцюжок ab<B>x. Тепер виконаємо згортання за допомогою другого правила й одержимо ланцюжок a<B>x. Нарешті, виконаємо згортання з використанням першого правила. Одержимо початковий символ граматики, отже, задана ланцюжок належить мові, породжуваному заданою граматикою.

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

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

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

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

Модель розпізнавача

Читання символів вхідного алфавіту здійснюється читаючою головкою, що після зчитування символу зрушується на одну позицію вправо. Прочитаний у такий спосіб символ подається на вхід пристрою керування, що може змінювати свій стан. Такий розпізнавач (A) може бути визначений сукупністю п'яти компонентів:

А = {P, S, s₀, ц, F},



де P - вхідний алфавіт розпізнавача, що містить символи, які записуються на вхідну стрічку,

S - множина станів розпізнавача,

s₀ - початковий стан, яким є один зі станів множини S,

ц - функція переходів, що задає відображення

ц: PЧS> S

F - множина кінцевих станів, що повинна бути підмножиною S,

Ця функція кожній парі: стан і вхідний символ ставить у відповідність стан розпізнавача. У функціональній формі вона записується так:

ц (s_i, p_k) = s_m.

На практиці функцію переходів задають у вигляді двовимірної таблиці, що називають таблицею переходів розпізнавача, або у вигляді орієнтованого графа, який називають діаграмою переходів розпізнавача. При побудові таблиці переходів її рядки відзначаються станами розпізнавача, а стовпці позначаються вхідними символами. У кожній клітині таблиці, що відповідає рядку, відзначеної станом s_i, і стовпцю, відзначеному вхідним символом p_k, записується стан s_m, обумовлений функцією переходів ц (s_i, p_k) = s_m. Прикладом таблиці переходів розпізнавача є таблиця. Стану розпізнавача в цій таблиці позначені буквами латинського алфавіту, а вхідний алфавіт складається із цифр 0 й 1.

Щоб побудувати діаграму переходів розпізнавача, потрібно кожному стану зіставити вершину графа й позначити цю вершину символом стану, а кожному переходу, обумовленому функцією ц (s_i, p_k) = s_m, дугу графа s_m, відзначену вхідним символом p_k і з'єднуючої вершини s_i, і s_m.

Робота розпізнавача може бути представлена у вигляді послідовності тактів. Щоб описати роботу розпізнавача, уведемо поняття конфігурації. Конфігурація розпізнавача визначається станом s_i і ще не прочитаною частиною вхідного ланцюжка б' на стрічці: (s_i, б').

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

Зміну конфігурацій позначають спеціальним символом і записують так:

(s_k,б) |> (s_i, б').

Якщо існує послідовність конфігурацій, що відповідає послідовності тактів роботи розпізнавача А

(s_i, б₁₎ |> (s_i2, б₂₎ |>… |> (s_ik, б_k),

то позначають її у такий спосіб:

(s_i1, б₁₎ |>^* (s_ik, б_k)

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

Конфігурація, утворена кінцевим станом з множина F і порожнім ланцюжком, називається кінцевою або заключною конфігурацією.

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

Множина ланцюжків L, що допускають распознавателем А, назвемо мовою, що допускають цим распознавателем L(А).

L(А) = {б | б* й (s₀, б) |> ^* (s_k, F) і s_k F}

Як ілюстрація розглянемо роботу розпізнавача А_1, що визначаться множинами: P = {0, 1}, S = {A, B, C, D}, F = {D}. Функція переходів цього розпізнавача задається таблицею 1.19.:

Таблиця переходів розпізнавача А₁

pk	0	1
A	B	A
D	C	A
C	D	C
D	-	-

Діаграма переходів розпізнавача А1

Робота розпізнавача для вхідного ланцюжка 01001 може бути представлена у вигляді послідовності конфігурацій (A, 01001) > (B, 1001) > (A, 001) > (B, 01) > (C, 1) > (C, 0), яка показує, що ланцюжок не допускається розпізнавачем А₁, оскільки він не досягає скінченного стану після прочитання всіх вхідних символів.

Уведені поняття дозволяють визначити зв'язок між формальними граматиками й розпізнавачами шляхом установлення відповідності мов, породжуваних граматиками, і мов, що допускають розпізнавачами.

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

Для кожного розпізнавача існує А-граматика, що породжує мову, що збігається з множиначю ланцюжків, що допускає розпізнавач.

Щоб показати справедливість цього твердження, розглянемо побудову граматики по заданій діаграмі переходів розпізнавача. Така побудова полягає в наступному. Для кожної пари станів розпізнавача X й Y, з'єднаних дугою, що виходить із X, що заходить в Y і позначеної вхідним символом p, побудуємо правило граматики виду <X>> a <Y>, якщо стан Y не є кінцевим станом розпізнавача, або - правило <X>> a, якщо Y - скінченний стан.

Отримана в такий спосіб множина правил визначає граматику, що породжує мову, що допускає заданим розпізнавачем. Дійсно, кожен породжуваний розпізнавачем ланцюжок L буде викликати послідовність переходів розпізнавача, а кожному переходу відповідає правило граматики, тому послідовність переходів при читанні символів ланцюжка L буде відповідати послідовності застосування правил граматики, тобто виводу цього ланцюжка в побудованій граматиці. Застосуємо описаний спосіб побудови до розпізнавача А₁. У результаті одержимо граматику зі схемою:

R= <A> > 1 <A>,<A> > 0 <B>, <B> > 1 <A>, <B> > 0 <C>, <C>> 1 <C>, <C>> 0.

Розглянемо ще один приклад побудови граматики для розпізнавача А₂, що заданий діаграмою переходів, зображеної на рис.

Діаграма переходів розпізнавача А2



Цей розпізнавач має однокінцевей стан, що збігається з його початковим станом F= {I}.

Цю обставину варто врахувати при побудові правила граматики, що відповідає переходу зі стану B у стан I.

Сама граматика, побудована по діаграмі розпізнавача А₂, має вигляд:

R=<I>>0<I>

<I>>1<A>

<A>>0<A>

<A>>1<B>

<B>>0<B>

<B>>1<I>

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

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

Щоб показати виправданість цього твердження, спочатку опишемо спосіб побудови розпізнавача по заданій граматиці.

Побудова передбачає виконання двох етапів: спочатку здійснюється перетворення заданої граматики, а потім побудова діаграми переходів розпізнавача.

Перетворення заданої граматики виконується в такий спосіб.

Доповнимо алфавіт V_А ще одним символом <Z>.Всі заключні правила граматики виду <A>> a перетворимо в правила виду <A>> a<Z>. Додамо правило <Z>> $. Інші правила залишимо без зміни.

Побудова діаграми переходів розпізнавача виконується за наступними правилами:

1) поставимо у відповідність кожному нетермінальному символу вузол графа,

2) для кожного правила <A>a<B> з'єднаємо дугою вузли A й B і відзначимо цю дугу символом a,

3) вузол, відзначений початковим символом граматики, приймемо як початковий вузол, а вузли, відзначені символом <Z>, як скінченні вузли графа (вузли, для яких є правила Z > $, уважаємо заключними).

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

Як приклад побудуємо розпізнавач для граматики Г_2.1

Г_2.1: R= {<I>> a <I>, <I>> a <A>, <A>> b <A>, <A>> b}

Після перетворення одержуємо граматику Г_2.1' і діаграму переходів шуканого розпізнавача у вигляді:

Г_2.1': R= {<I>> a <I>, <I>> a <B>, <B>> b<B>, <B>> b<Z>, <Z>> $}

Діаграма розпізнавача A₃, побудована по цій граматиці, зображена на рис.

Діаграма переходів розпізнавача A3, побудованого для правобічної граматики Г2.1'

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

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

a) позначення початкової й кінцевої вершин на діаграмі переходів треба поміняти місцями,

b) поміняти напрямок всіх дуг на діаграмі переходів на протилежне.

Якщо виконати описані перетворення для діаграми переходів розпізнавача А₃, побудованого по правобічній граматиці Г_2.1', то одержимо діаграму розпізнавача А₄, наведену на рис.

Діаграма переходів розпізнавача A4, що відповідає лівосторонній граматиці

Цій діаграмі відповідає лівостороння граматика, схема якої має вигляд:

R = {<I>><B>b, <B>><B> b, <B>><Z> a, <Z>><Z> a}.

1.5 Автомати з вихідним перетворювачем. Автомати Мілі й Мура

Автомати з вихідним перетворювачем являють собою сукупність наступних шести об'єктів:

A = <P, S, s₀, ц, W, ш>

W - вихідний алфавіт

ш - функція виходів

Існує дві математичні моделі автомата (автомат Мура й Мілі) обидві модели можна представити у вигляді двох частин - формулювач передісторії та вихідний перетворювач.

P S W

Автомат Мура

В автоматі Мура здійснюється відображення S >W, тобто кожній букві стану ставиться буква вихідного алфавіту.

W_i = ш(s_i)

W_i (t+1)= ш (s(t+1)) - новий вихідний символ визначається новим станом.

Автомат Мілі

W_k = ш(P_i, S_j)

W (t+1) = ш (P(t)_, S(t))

Нове вихідне слово в автоматі Міля визначається станом, у якому був автомат і вихідне слово, що надійшло на автомат.

Був у стані > надійшов у стан.

Задання автомата Мура:

A: <P, W, S, s₀, ц, ш>

В автоматі Мура ш залежить тільки від станів.

Автомат як Мура, так і Міля задається шістьома параметрами.

P, W, S - задаються у вигляді множин

s₀ - початковий стан указується як буква алфавіту S

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

Функція ш - також може бути представлена тими ж трьома способами.

a) перерахування

ц: S_{1 =} ц(S_0, S₁) ш: W₁ = ш (S₁)

ц: S_{2 =} ц(S_1, S₁) ш: W₂ = ш (S₂)

ц: S_{k =} ц(S_k, S_k-1) ш: W₀ = ш (S₀)

b) табличний спосіб

Wi	Pi	Pi	P0	P1	P2	…	Pn-1
W0	S0	Si	Sj	…	…	…	…
W1	S1	…	…	…	…	…	…
Wl-1	Sm-1	S0	Sk	.	…	…	…

Дана таблиця одна визначає дві функції, тому що W_i залежить тільки від S_i. Таблиця називається «відзначеною» таблицею.

Кількість W й S може бути різною, тому що різним станам може бути поставлене у відповідність та сама вихідна буква.

c) графічний спосіб

Размещено на http://www.allbest.ru/



Автомат Милі P, W, S, s₀ - задається аналогічно автомату Мура.

Функції виходу задаються трьома способами:

a) перерахування

ц:

S_{1 =} ц(S₀, P₁) - попередній вплив - новий стан

S_{2 =} ц(S₁, P₂)

…

S_{m-1 =} ц(S_m-2, P₀)

ш:

W₁ = ш (S₀, P₁)

W₂ = (S₁, P₂)

…

W_l-1 = ш (S_m-1, P₀)

b) Табличний спосіб

Pj	P0	P1	…	Pn-1
Si
S0	S1	S2	…	S3
S1	S2	S3	…	…
…	…	…	…	…
Sm-1	S0	…	…	…

Таблиця виходів для ш

Pj	P0	P1	…	Pn-1
Si
S0	W0	W1	…	Wl-1
S1	W1	W2	…	…
…	…	…	…	…
Sm-1	W0	…	…	…

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

Pj	P0	P1	…	Pn-1
Si
S0	S1/W0	S2/W1	…	S3/Wl-1
S1	S3/W1	S2/W2	…	…
…	…	…	…	…
Sm-1	S0/W0	…	…	…

c) Графічний спосіб

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

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

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

2. Використання кінцевих автоматів для розпізнавання регулярних виразів

2.1 Мови й регулярні вирази

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

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

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

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

Як предметне позначення деякого об'єкта з мови, приведемо приклад ідентифікатора, що представляє певним чином побудований ланцюжок символів - букв (Б) або цифр (Ц), причому першим символом у ланцюжку є буква, а потім послідовність букв і цифр. граматики, що породжують, у цьому випадку визначають цю конструкцію як

G [<ідентифікатор>]:

V_T = {Б, Ц}, V_N = {<ідентифікатор>, <хвіст ідентифікатора>, <Б Ц>}

P:

1. < ідентифікатор >> Б < хвіст ідентифікатора >

2. < хвіст ідентифікатора >><Б Ц>< хвіст ідентифікатора > | L

<БЦ>>Б | Ц

Мова, породжувана цією граматикою L (G[<ідентифікатор >]) і є

ідентифікатором. Ця ж мова ідентифікаторів можна задати простіше у вигляді простої формули

R₁ = Б (Б | Ц)^*,

відповідно мова, визначена формулою або регулярним виразом R₁ визначена як множина L(R₁) = {Б (Б|Ц)^*}, де знак * - означає ітерацію над буквою й цифрою або замикання Кліні.

Таке просте задання мови не вимагає компонентів V_N, P, Z й у загальному самої граматики G[Z]. Необхідно тільки задати словник S =V_T і саме вирази (формулу) R, що визначає мова.

Так само просто можна визначити цілі без знака, як нескінченну ітерацію цифр позиційної системи числення R₂ = a b^*, де a - це всі цифри без 0 - [1 - 9], b - всі цифри - [0 - 9].

Відповідно мова цілих представлена дуже просто - L(R₂) = {ab^*}.

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

Регулярні вирази широко використаються у всіх процесорах, у яких потрібен шаблоновий-орієнтований пошук. У першу чергу - це лексичні аналізатори. Для виділення шаблонів - ідентифікаторів, числових констант, ключових слів і т.д. використають регулярні вирази. Наприклад, у системі LEX генератора лексичних аналізаторів всі шаблони визначаються регулярними виразими, а генератор в LEX генерує ефективний скінченний автомат, що розпізнає шаблони.

2.2 Автоматні граматики й регулярні вирази

Розглянемо мову L = {aⁿbⁿ | nі1}. Множина рядків цієї мови є підмножиною рядків мови, певного регулярного виразу R = aa^*bb^*. Дійсно в L всі рядки складаються тільки з тих послідовностей a й b, у яких символи a повторюються один і більше раз, за ними треба послідовність символів b, які точно повторюють попереднє їм кількість символів а. Для L(R) - ланцюжка включають всі послідовності символів а, за яких треба b, причому й таких у тому числі послідовностей, де кількість може бути й не рівним b. Тому в загальному випадку регулярний вираз R відповідає мові, породжуваному граматикою G[I]; такому що L (G[I]) = {aⁿb^m| n, m і 1} із графом переходів представленим на рис. 2.1.

Регулярний вираз R відповідний мові, породжуваної граматики G[I] із графом переходів

Відповідна автоматна граматика легко підбирається по графу G[I]:

I>a

B>Ab | b

C>a | e

У такий спосіб автоматна граматика G[I] породжує ту ж мову, що й мова L(R), визначений регулярним виразим L(R) = L (G[I]). У цьому випадку можна говорити про еквівалентності регулярного виразу R й автоматної граматики G[I]. Тому автоматну граматику G[I] ще називають регулярною, що й було зроблено в класифікації Хомского.

Змістовними прикладами використання регулярного виразу (РВ) є побудовані на принципах РВ сучасні лексичні аналізатори. На поняттях РВ і регулярних визначень побудована мова специфікацій генератора лексичних аналізаторів LEX. Багато конструкцій ОС UNIX використають РВ. Всі шаблони, де немає збалансованих конструкцій можуть легко представлятися регулярними виразами. Збалансованими конструкціями в цьому випадку є конструкції типу {a ⁿbⁿ| n>=1}. До таких конструкцій належить, наприклад, інфіксна форма арифметичних скобкових виразів.

Висновок

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

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

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

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

Список джерел

1 Бронштейн, И.Н. Справочник по математике для инженеров и учащихся вузов / И.Н. Бронштейн, К.А. Семендяев. - М.: Наука, 2007. - 708 с.

2 Дехтярь М.И. Введение в схемы, автоматы и алгоритмы. - М.: Наука, 2002. С. 642.

3 Коган Д.И., Бабкина Т.С. Концепции конечного автомата и регулярного языка. Операции над регулярными языками. М.: Наука, 2000.

4 Конечный автомат-http://ru/wikipedia.org/wiki/Конечный_автомат.

5 Лупал А.М. Теория автоматов. Учебное пособие/СПбГУАП. - СПб., 2000. - 120 с., ил.

6 Мозговой, М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. / М.В. Мозговой. - М.: Наука и Техника, 2006. С. 320.

7 Семакин, И.Г. Основы программирования. / И.Г. Семакин, А.П. Шестаков. - М.: Мир, 2006. C. 346.

8 Симанков, В.С. Основы функционального программирования / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. - Краснодар: Куб ГТУ, 2002. - 160 с.

9 Регулярные выражения - http: // www.spo-theory.ru/ yazyki-i-regulyarnye-vyrazheniya/4-6-celesoobraznost-perehoda-ot-nka-k-dka.html

10 Фридл Дж. Регулярные выражения. СПб.: Питер, 2002.

Размещено на Allbest.ru