- •Розділ 7 Основи теорії кодування План викладення матеріалу
- •7.1. Алфавітне й рівномірне кодування
- •7.2. Достатні умови однозначності декодування. Властивості роздільних кодів
- •7.3. Оптимальне кодування
- •7.4. Коди, стійкі до перешкод. Коди Хемінга
- •8.2. Алгебри булевих функцій
- •8.3. Спеціальні форми зображення булевих функцій в алгебрах Буля і Жегалкіна
- •8.3.1. Диз'юнктивні нормальні форми
- •8.3.2. Кон'юнктивні нормальні форми
- •8.3.3. Поліном Жегалкіна
- •8.4. Повнота і замкненість
- •8.4.1. Функціонально повні системи
- •8.4.2. Замкнені класи
- •8.4.4. Послаблена функціональна повнота
- •8.4.5. Передповні класи
- •8.5. Мінімізація булевих функцій
- •8.5.1. Основні результати
- •8.5.2. Методи побудови скороченої днф
- •8.5.3. Побудова тупикових днф
- •8.5.4. Властивості скороченої днф
- •8.5.5.Метод карт Карно побудови мінімальних днф
- •8.6. Реалізація булевих функцій схемами з функціональних елементів
- •Комп'ютерні проекти
- •Література
- •9.2. Формальні породжувальні граматики
- •9.3. Типи граматик (ієрархія Хомські)
- •9.4. Дерева виведення
- •9.5. Форми Бекуса-Наура
- •9.6. Скінченні автомати з виходом
- •9.7. Скінченні автомати без виходу
- •9.8. Подання мов
- •Комп'ютерні проекти
- •Література
- •Розділ 10
- •План викладення матеріалу
- •10.1. Основні вимоги до алгоритмів
- •10.2. Машини Тьюрінга
- •10.3. Обчислення числових функцій на машинах Тьюрінга
9.7. Скінченні автомати без виходу
Одне з найважливіших застосувань скінченних автоматів є подання (розпізнавання) мов. Це застосування має фундаментальне значення у дослідженні та побудові компіляторів для мов програмування. У прикладі 9.23 описано, як скінченний автомат з виходом може розпізнавати мову: він видає на виході 1, якщо вхідний ланцюжок належить мові, і 0 у протилежному випадку. Проте є інший тип скінченних автоматів, спеціально призначений для подання мов. Замість виходу ці автомати мають множину заключних станів. Ланцюжок допускається автоматом, якщо він переводить автомат з початкового стану в один із заключних станів.
Скінченним автоматом без виходу називають системуM=(S, І, f, s0,F), у якійS-скінченна множина станів, І-скінченний вхідний алфавіт,f: S×I→S- функція переходів, визначена на декартовому добуткуS×I,s0∈S— початковий стан, F⊂S— множина заключних (або приймаючих) станів.
Елементи вхідного алфавіту, як і раніше, називаютьвхідними символами абовходами.
Таблиця 9.5
-
f
Стан
Вхід
0
1
s0
s0
s1
s1
s0
s2
s2
s0
s0
s3
s2
s1
Рис. 9.10
Скінченні автомати без виходу можна задавати таблицями станів або діаграмами станів. Заключні стани на діаграмі зображають подвійними кружечками. Зазначимо, що в автоматах без виходу є тільки входи (символи вхідного алфавіту І), тому на дугах діаграми записують тільки їх.
Оскільки далі ми будемо розглядати лише скінченні автомати без виходу, то називатимемо їх скінченними автоматами, або просто автоматами.
Приклад 9.24. Зобразимо діаграму станів для скінченного автоматаM=(S, І, f, s0,F),деS={s0,s1,s2,s3}, I={0,1}, F={s0,s3}.Функцію переходів задано табл. 9.5. Діаграму станів зображено на рис. 9.10. Наголосимо, що оскільки обидва входи 0 та 1 переводять автомат зі стануs2 у станs0 то замість двох дуг s2від до s0використано лише одну дугу, на якій написано два входи: 0 та 1.▲
Функцію переходівfможна розширити й визначити її для всіх пар станів і ланцюжків. У такому разі нехай𝛼=x1x2…xk-ланцюжок зI*. Тодіf(s1, α)-стан, обчислений із використанням послідовних символів ланцюжка α зліва направо як вхідних символів, починаючи зі стану s1. Процес іде так:s2=f(s1, x1);s3=f(s2, x2),... Нарешті приймаємоf(s1, α)=sK=f(sK, xK).
Говорять, що ланцюжокαдопускається (приймається)скінченним автоматомM=(S, І, f, s0,F)якщо він переводитьпочатковий стан s0 у заключний стан - це означає, що стану(s0, α) є елементом множини F. Мова, що розпізнається автоматом М, позначаєтьсяL(М), - це множина всіх ланцюжків, які допускаються автоматом М. Два автомати називають еквівалентними, якщо вони розпізнають одну й ту саму мову.
Рис. 9.11
Рис. 9.12
Приклад 9.25. Визначимо мову, яка розпізнається скінченним автоматом М1 з діаграмою станів на рис. 9.11.
Автомат М1 має лише один заключний станs1. Тільки два ланцюжки переводятьs1 в s2; цими ланцюжками є 1 та 01. Отже,L(M1)={1,01}.▲
Приклад 9.26. Визначимо мову, яка розпізнається скінченним автоматом М2 з діаграмою станів на рис. 9.12.
Заключними станами автомата М2 є s0 та s3. Ланцюжками, які переводятьs0 самого в себе, є порожній ланцюжок λ, а також ланцюжки з довільної кількості нулів: 0, 00, 000. ... Ланцюжки, які переводять s0 в s3складаються з деякої кількості нулів, після яких є 10 і довільний ланцюжок β з нулів та одиниць. Отже,
- довільний ланцюжок}.▲
Розглянуті скінченні автомати без виходу називають детермінованими, оскільки для кожної пари стан-вхід існує єдиний наступний стан, заданий функцією переходів. Є й інший тип автоматів без виходу - це недетерміновані автомати. У таких автоматах може бути декілька можливих наступних станів для кожної пари стан-вхідний символ.
Недетермінованим скінченним автоматом без виходу називають систему M=(S, І, f, s0,F), у якійS - скінченна множина станів,I -скінченний вхідний алфавіт,f-функція переходів, яка кожній парі стан-вхід ставить у відповідність множину станів,s0∈S -початковий стан, F⊂S- множина заключних станів.
Зазначимо, що єдиною відмінністю між недетермінованим і детермінованим автоматами є тип значень функції переходівf. Для недетермінованого автомата це множина станів (ця множина може бути й порожньою), а для детермінованого - один стан.
Недетермінований скінченний автомат задають таблицею або діаграмою станів. У разі використання таблиці для кожної пари стан - вхід записують множину всіх можливих наступних станів (якщо вона порожня, то ставлять прочерк). У діаграмі переходів уводять дуги з кожного стану до всіх можливих наступних станів, записуючи на цих дугах входи, які спричинюють переходи одного стану в інший.
Приклад 9.27. На рис. 9.13 і у табл. 9.6 зображено відповідно діаграму і таблицю станів деякого недетермінованого автомата. ▲
Таблиця 9.6
-
Стан
f
Вхід
0
1
s0
s0, s2
s1
s1
s3
s4
s2
-
s4
s3
s3
-
s4
s3
s3
Тепер визначимо, як недетермінований скінченний автомат допускає (приймає) ланцюжок𝛼=x1x2…xk.Перший вхідний символ х1 переводить стан s0 у множинуS1, яка може містити понад один стан. Наступний вхідний символх2 переводить кожний зі станів множини S1 у деяку множину станів, і нехай S2 є об'єднанням цих множин. Цей процес продовжують, вибираючи на кожній стадії всі стани, отримані з використанням поточного вхідного символу і всіх станів, отриманих на попередній стадії. Недетермінований скінченний автоматдопускає (приймає) ланцюжок а, якщо у множині станів, отриманій з початкового стану під дією ланцюжка а, є заключний стан. Мова, що розпізнаєтьсянедетермінованим скінченним автоматом - це множина всіх ланцюжків, які допускаються цим автоматом.
Приклад 9.28. Знайдемо мову, яка розпізнається недетермінованим скінченим автоматом з рис. 9.13.
Оскільки s0 є заключним станом, і вхід 0 переводить s0 у себе, то автомат допускає ланцюжки λ, 0,00,000,0000,... Стан також заключний, і нехай s4 є у множині станів, що досягаються зі стану s0 з ланцюжком а на вході. Тоді ланцюжок а допускається. Такими ланцюжками є 0n01 та 0n11, де n=0,1,2,... Оскільки інших заключних станів немає, то мова, яка розпізнається цим недетермінованим автоматом, є такою: {0n, 0n01, 0n11| n=0,1,2,...}.
Важливо зазначити: якщо мова розпізнається недетермінованим автоматом, то вона також розпізнається детермінованим автоматом.
Теорема 9.1. Якщо моваL розпізнається недетермінованим скінченним автоматом М0, то L розпізнається також детермінованим скінченним автоматомМ1.
Доведення. Опишемо, як автоматМ1 конструюють за автоматом М0. Кожний станM1 будують у вигляді підмножини станів М0. Символом початкового стану автоматаМ1 є {s0} тобто це множина, єдиним елементом якої є початковий станs0 автоматаМ0. ВхіднийалфавітМ1 той самий, що іМ0. Нехай задано стан автоматаМ1.Вхідний символх переводить цей стан в об'єднання множин наступних станів для елементів цієї множини, тобто в .Стани автоматаМ1 - це всі такі підмножини множини S (множини станів автомата М0), які отримують зазначеним способом, починаючи від . (Отже, може бути до2n станів у детермінованому автоматі, де п -кількість станів у недетермінованому автоматі, проте, як звичайно, їх буває значно менше). Заключними станами автоматаМ1 є ті підмножини, які містять заключні стани автоматаМ0.
Нехай вхідний ланцюжок а допускається автоматомМ0. Тоді один зі станів, який досягається з при вході а, буде заключним станом. Це означає, що в М1 ланцюжок а веде з {s0} до такої підмножини станів автомата М0, яка містить заключний стан. Ця підмножина є за побудовою заключним станом автомата М1 отже, ланцюжок α також допускається автоматомМ1. Якщо ж вхіднийланцюжок β не допускається автоматом М0, то цей ланцюжок не веде до жодного із заключних станів М0. Звідси випливає, що β не веде з {s0} до жодного заключного стану М1. ▲
З теореми 1 випливає, що недетерміновані скінченні автомати розпізнають ті самі мови (множини ланцюжків), що й детерміновані скінченні автомати. Проте є причини розглядати недетерміновані автомати. Вони часто компактніші, і їх легше побудувати, ніж детерміновані. Крім того, хоча недетермінований автомат завжди можна перетворити у детермінований, останній може мати експоненціально більше станів. На щастя, такі випадки досить рідкісні.
Приклад 9.29.Побудуємо детермінований скінченний автомат, який розпізнає ту саму мову, що й недетермінований автомат з рис. 9.13.
Детермінований автомат, зображений на рис. 9.14, його стани є підмножинами станів недетермінованого автомата з рис. 9.13. Їх отримують так, як це описано у доведенні теореми 9.1. Зокрема, вхід 0 переводить стан {s0} у стан {s0,s2} в детермінованому автоматі, оскільки s0 у разі входу 0 переходить у самого себе і в s2 в недетермінованому автоматі. Аналогічно, вхід 1 переводить множинуу множину {s1, s4}, оскільки у разі входу 1 в недетермінованому автоматі s0 переходить в s1,аs2– вs4. Нарешті, вхід 0 переводить
Рис. 9.14
множину {s1, у4} у множину {s3}, оскільки в недетермінованому автоматі вхід 0 переводить обидва станиs1таs4у станs3.Усі підмножини, які отримують таким способом, є станами детермінованого скінченного автомата з рис. 9.14. Наголосимо, що одним із станів цього автомата є порожня множина - множина станів, в які вхід 1 переводить {s3}. Початковий стан - {s0}, а заключними є всі стани, які містять s0або s4. ▲