Скінченні автомати без виходу

Одне з найважливіших застосувань скінченних автоматів є подання (розпізнавання) мов. Це застосування має фундаментальне значення у дослідженні та побудові компіляторів для мов програ­мування. У прикладі 9.23 описано, як скінченний автомат з виходом може розпізнавати мову: він видає на виході 1, якщо вхідний ланцюжок належить мові, і 0 у протилежному випадку. Проте є інший тип скінченних автоматів, спеціально призначений для подання мов. Замість виходу ці автомати мають множину заключ­них станів. Ланцюжок допускається автоматом, якщо він перево­дить автомат з початкового стану в один із заключних станів.

Скінченним автоматом без виходу називають систему M =(S, І, f, s₀, F), у якій S -скінченна множина станів, І -скінченний вхідний алфавіт, f: S × I→ S - функція переходів, визначена на декартовому добутку S × I, s ₀∈ S — початковий стан, F ⊂ S — множина заключних (або приймаючих) станів.

Елементи вхідного алфавіту, як і раніше, називаютьвхідними символами абовходами.

Таблиця 9.5

Рис. 9.10

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

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

Приклад 9.24. Зобразимо діаграму станів для скінченного автомата M =(S, І, f, s₀, F), де S ={ s ₀, s ₁, s ₂, s ₃}, I ={0, 1}, F ={ s ₀, s ₃}.Функцію переходів задано табл. 9.5. Діаграму станів зображено на рис. 9.10. Наголосимо, що оскільки обидва входи 0 та 1 перево­дять автомат зі стану s ₂ у стан s ₀ то замість двох дуг s ₂від до s ₀використано лише одну дугу, на якій написано два входи: 0 та 1.▲

Функцію переходів f можна розширити й визначити її для всіх пар станів і ланцюжків. У такому разі нехай𝛼 = x ₁ x ₂… x_k -ланцюжок з I *. Тоді f (s ₁, α)-стан, обчислений із використанням послідовних символів ланцюжка α зліва направо як вхідних символів, почи­наючи зі стану s ₁. Процес іде так: s ₂= f (s ₁, x ₁); s ₃= f (s ₂, x ₂),... Нареш­ті приймаємо f (s ₁, α)= s_K = f (s_K, x_K).

Говорять, що ланцюжокα допускається (приймається)скінченним автоматом M =(S, І, f, s₀, F)якщо він переводитьпочатковий стан s ₀ у заключний стан - це означає, що стану(s ₀, α) є елементом множини F. Мова, що розпізнається автоматом М, позначаєтьсяL(М), - це множина всіх ланцюжків, які допускаються автоматом М. Два автомати називають еквівалентними, якщо вони розпізнають одну й ту саму мову.

Рис. 9.11

Рис. 9.12

Приклад 9.25. Визначимо мову, яка розпізнається скінченним автоматом М₁ з діаграмою станів на рис. 9.11.

Автомат М ₁ має лише один заключний стан s ₁. Тільки два ланцюжки переводять s ₁ в s ₂; цими ланцюжками є 1 та 01. Отже, L (M ₁)={1, 01}.▲

Приклад 9.26. Визначимо мову, яка розпізнається скінченним автоматом М₂ з діаграмою станів на рис. 9.12.

Заключними станами автомата М₂ є s ₀ та s ₃. Ланцюжками, які переводять s ₀ самого в себе, є порожній ланцюжок λ, а також лан­цюжки з довільної кількості нулів: 0, 00, 000.... Ланцюжки, які переводять s ₀ в s ₃складаються з деякої кількості нулів, після яких є 10 і довільний ланцюжок β з нулів та одиниць. Отже,

- довільний ланцюжок}.▲

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

Недетермінованим скінченним автоматом без виходу нази­вають систему M =(S, І, f, s₀, F), у якійS - скінченна множина станів, I -скінченний вхідний алфавіт, f-функція переходів, яка кожній парі стан-вхід ставить у відповідність множину станів, s ₀∈ S -початковий стан, F ⊂ S - множина заключних станів.

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

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

Приклад 9.27. На рис. 9.13 і у табл. 9.6 зображено відповідно діаграму і таблицю станів деякого недетермінованого автомата. ▲

Таблиця 9.6

Тепер визначимо, як недетермінований скінченний автомат допускає (приймає) ланцюжок𝛼 = x ₁ x ₂… x_k. Перший вхідний символ х ₁ переводить стан s ₀ у множину S ₁, яка може містити понад один стан. Наступний вхідний символх₂ переводить кожний зі станів множини S ₁ у деяку множину станів, і нехай S ₂ є об'єднанням цих множин. Цей процес продовжують, вибираючи на кожній стадії всі стани, отримані з використанням поточного вхідного символу і всіх станів, отриманих на попередній стадії. Недетермінований скінченний автоматдопускає (приймає) ланцюжок а, якщо у множині станів, отриманій з початкового стану під дією лан­цюжка а, є заключний стан. Мова, що розпізнаєтьсянедетермінованим скінченним автоматом - це множина всіх ланцюжків, які допускаються цим автоматом.

Приклад 9.28. Знайдемо мову, яка розпізнається недетермінованим скінченим автоматом з рис. 9.13.

Оскільки s ₀ є заключним станом, і вхід 0 переводить s ₀ у себе, то автомат допускає ланцюжки λ, 0, 00, 000, 0000,... Стан також заключний, і нехай s ₄ є у множині станів, що досягаються зі стану s ₀ з ланцюжком а на вході. Тоді ланцюжок а допускається. Такими ланцюжками є 0 ⁿ 01 та 0 ⁿ 11, де n =0, 1, 2,... Оскільки інших заключ­них станів немає, то мова, яка розпізнається цим недетермінованим автоматом, є такою: {0 ⁿ, 0 ⁿ 01, 0 ⁿ 11| n =0, 1, 2,...}.

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

Теорема 9.1. Якщо моваL розпізнається недетермінованим скінченним автоматом М ₀, то L розпізнається також детерміно­ваним скінченним автоматомМ_1.

Доведення. Опишемо, як автоматМ₁ конструюють за автоматом М₀. Кожний станM₁ будують у вигляді підмножини станів М ₀. Сим­волом початкового стану автоматаМ₁ є { s ₀} тобто це множина, єдиним елементом якої є початковий станs₀ автоматаМ₀. ВхіднийалфавітМ₁ той самий, що іМ₀. Нехай задано стан автоматаМ₁. Вхідний символх переводить цей стан в об'єднання множин наступних станів для елементів цієї множини, тобто в .Стани автоматаМ₁ - це всі такі підмножини множини S (множини станів автомата М ₀), які отри­мують зазначеним способом, починаючи від. (Отже, може бути до2ⁿ станів у детермінованому автоматі, де п -кількість станів у недетермінованому автоматі, проте, як звичайно, їх буває значно менше). Заключними станами автоматаМ₁ є ті підмножини, які містять заключні стани автоматаМ₀.

Нехай вхідний ланцюжок а допускається автоматомМ₀. Тоді один зі станів, який досягається з при вході а, буде заключним станом. Це означає, що в М ₁ ланцюжок а веде з { s ₀} до такої підмно­жини станів автомата М ₀, яка містить заключний стан. Ця підмножина є за побудовою заключним станом автомата М ₁ отже, ланцю­жок α також допускається автоматомМ₁. Якщо ж вхіднийланцюжок β не допускається автоматом М₀, то цей ланцюжок не веде до жодного із заключних станів М₀. Звідси випливає, що β не веде з { s ₀} до жодного заключного стану М₁. ▲

З теореми 1 випливає, що недетерміновані скінченні автомати розпізнають ті самі мови (множини ланцюжків), що й детерміновані скінченні автомати. Проте є причини розглядати недетерміновані автомати. Вони часто компактніші, і їх легше побудувати, ніж детер­міновані. Крім того, хоча недетермінований автомат завжди можна перетворити у детермінований, останній може мати експоненціально більше станів. На щастя, такі випадки досить рідкісні.

Приклад 9.29.Побудуємо детермінований скінченний автомат, який розпізнає ту саму мову, що й недетермінований автомат з рис. 9.13.

Детермінований автомат, зображений на рис. 9.14, його стани є підмножинами станів недетермінованого автомата з рис. 9.13. Їх отримують так, як це описано у доведенні теореми 9.1. Зокрема, вхід 0 переводить стан { s ₀} у стан { s ₀, s ₂} в детермінованому автоматі, оскільки s ₀ у разі входу 0 переходить у самого себе і в s ₂ в недетермі­нованому автоматі. Аналогічно, вхід 1 переводить множинуу множину { s ₁, s ₄}, оскільки у разі входу 1 в недетермінованому автоматі s ₀ переходить в s ₁, а s ₂– в s ₄. Нарешті, вхід 0 переводить

Рис. 9.14

множину { s _1, у ₄} у множину { s ₃}, оскільки в недетермінованому автоматі вхід 0 переводить обидва станиs₁таs₄у станs₃.Усі підмножини, які отримують таким способом, є станами детерміно­ваного скінченного автомата з рис. 9.14. Наголосимо, що одним із станів цього автомата є порожня множина - множина станів, в які вхід 1 переводить { s ₃}. Початковий стан - {s₀}, а заключними є всі стани, які містять s ₀або s ₄. ▲