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

38.1. Скінченні автомати з виходом

Означення 38.1. Скінченним автоматом називають систему M = (S, I, O, f, g, s₀), у якій S – скінченна множина станів, I – скінченна множина, яку називають вхідним алфавітом, O – скінченна множина, яку називають вихідним алфавітом, f: SI  S – функція переходів, g: SI  O – функція виходів, s₀  S – виділений елемент, який називають початковим станом.

Елементи вхідного алфавіту називають вхідними символами, або входами, а вихідного – вихідними символами, або виходами. Рівність f(s_i, x) = s_j означає, що в разі входу x автомат, який перебуває в стані s_i, переходить у стан s_j, а рівність g(s_i, x) = y – що в цьому разі на виході з’являється y; тут s_i, s_j  S, x  I, y  O.

Оскільки функції f і g означено на скінченних множинах, то їх можна задавати таблицями. Зазвичай дві таблиці зводять у таблицю станів. Вона містить значення функції переходів f і функції виходів g для всіх пар (s, x), де s  S, x  I.

Наприклад, у табл. 38.1 задано функції переходів і виходів для автомата з множиною станів S = {s₀, s₁, s₂, s₃} та вхідним і вихідним алфавітами I = {0, 1}, O = {0, 1}.

Стан	f		g
	Вхід		Вхід
	0	1	0	1
s0	s1	s0	1	0
s1	s3	s0	1	1
s2	s1	s2	0	1
s3	s2	s1	0	0

Табл. 38.1.

Ще один поширений і наочний спосіб подання автомата  за допомогою орієнтованого мультиграфа, який називають діаграмою станів. Вершини графа відповідають станам; якщо f(s_i, x_j) = s_k та g(s_i, x_j) = y_r, то з вершини s_i у вершину s_k веде дуга з позначкою x_j, y_r. Тут x_j  I, y_r  O. Діаграму станів для автомата, заданого табл. 38.1, показано на рис. 38.1.

Рис. 38.1.

Для автомата M його функцію виходів g можна означити не тільки на множині I всіх вхідних символів (букв), а й на множині I* всіх вхідних ланцюжків (слів). Розглянемо вхідний ланцюжок  = x₁x₂…x_k. Під час його обробки автомат спочатку переходить зі стану s₀ в стан s₁, де s₁ = f(s₀, x₁), потім у стан s₂, де s₂ = f(s₁, x₂), і цей процес триває до досягнення стану s_k = f(s_k–1, x_k). Тут x_k – останній символ вхідного ланцюжка. Ця послідовність переходів у нові стани формує вихідний ланцюжок  = y₁y₂…y_k, де y₁ = g(s₀, x₁) – вихідний символ, який відповідає переходу з s₀ в s₁, y₂ = g(s₁, x₂) – вихідний символ, що відповідає переходу з s₁ в s₂, і так до отримання вихідного символу y_k = g(s_k–1, x_k). Загалом y_j = g(s_j–1, x_j) для j = 1, 2, ..., k. Отже, ми можемо розширити означення функції виходів на вхідні ланцюжки так, що g(a) = , де вихідний ланцюжок  відповідає вхідному ланцюжку .

Знайдемо вихідний ланцюжок, який видає скінченний автомат, зображений на рис. 38.1, якщо вхідний ланцюжок — 101001. Автомат видає на виході ланцюжок 011110. Послідовність його станів і вихідних символів наведено в табл. 38.2.

---

Вхід	1	0	1	0	0	1
Стан	s0	s0	s1	s0	s1	s3
Вихід	0	1	1	1	1	0
Новий стан	s0	s1	s0	s1	s3	s1

Табл. 38.2.

Означення 38.2. Відповідність, яка відображає вхідні ланцюжки  автомата M у вихідні ланцюжки  описаним вище способом, називають автоматним відображенням, а також автоматним оператором M.

Якщо результат застосування цього оператора до ланцюжка   вихідний ланцюжок , то це позначають M() = . Кількість символів у ланцюжку , як завжди, називають довжиною ланцюжка  та позначають || чи l().

Автоматне відображення має дві властивості.

1. Ланцюжки  та  = M() мають однакову довжину: || = || (збереження довжини).

2. Якщо  = ₁₂ й M(₁₂) = ₁₂, де |₁| = |₁|, то M(₁) = ₁, тобто образ відрізка довжиною l дорівнює відрізку образу з такою самою довжиною.

Властивість 2 означає, що автоматні оператори  це оператори без випередження, тобто такі, котрі, обробляючи ланцюжок зліва направо, “не підглядають уперед”: i-та буква вихідного ланцюжка залежить тільки від перших i букв вхідного ланцюжка. Приклад оператора з випередженням  той, який ланцюжку  = x₁x₂…x_k ставить у відповідність ланцюжок x_k…x₁x₂, перша буква вихідного ланцюжка тут дорівнює останній букві вхідного ланцюжка. Зазначимо, що ці дві властивості  це не достатні умови автоматності відображення: існують відображення, які задовольняють умови 1 і 2, але не реалізовані в скінченному автоматі.

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

Побудуємо скінченний автомат для додавання двох цілих додатних чисел у двійковій системі. Візьмемо числа (x_n…x₁x₀)₂ та (y_n…y₁y₀)₂. Додавши розряди x₀ та y₀, отримаємо розряд суми z₀ та біт перенесення c₀, який дорівнює 0 чи 1. Потім додамо розряди x₁та y₁ і біт перенесення c₀. Одержимо розряд суми z₁ та біт перенесення c₁. Процедуру продовжуємо до стадії підсумування розрядів x_n та y_n і попереднього біта перенесення c_n-1; отримаємо розряд суми z_n і біт перенесення c_n, який дорівнює розряду суми z_n+1.

Вхідний алфавіт автомата складається з чотирьох символів: I = {00, 01, 10, 11}. Вони потрібні для подання можливих значень x_i й y_i i-го розряду обох доданків. Вихідний алфавіт O = {0, 1}, множина станів S = {s₀, s₁}. Стан s₀ відповідає ситуації, коли немає одиниці перенесення з попереднього розряду; цей стан початковий. Стан s₁ відповідає наявності одиниці перенесення з попереднього розряду. Розв’язок наведено у вигляді таблиці станів (табл. 38.3) та діаграми станів (рис. 38.2).

---

Стан	f				g
	Вхід				Вхід
	00	01	10	11	00	01	10	11
s0	s0	s0	s0	s1	0	1	1	0
s1	s0	s1	s1	s1	1	0	0	1

Табл. 38.3.

Рис. 38.2.

Розглянуті автомати називають автоматами Мілі. Уперше їх уведено 1955 р. Є також інший тип автоматів із виходом – так звані автомати Мура, запроваджені 1956 р. У цих автоматах вихід залежить лише від стану, а не від вхідного сигналу.

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

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

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

Означення 38.3. Скінченним автоматом без виходу називають систему M = (S, I, f, s₀, F), у якій S – скінченна множина станів, I – скінченний вхідний алфавіт, f: SI  S – функція переходів, означена на декартовому добутку SI, s₀  S – початковий стан, F  S – множина заключних (або приймаючих) станів.

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

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

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

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

Означення 38.4. Говорять, що скінченний автомат M = (S, I, f, s₀, F) допускає (приймає) ланцюжок , якщо він переводить початковий стан s₀ в заключний стан; це означає, що стан f(s₀, )  елемент множини F.

Означення 38.5. Мова L(M), яку розпізнає автомат M,  це множина всіх ланцюжків, які допускає автомат M. Два автомати називають еквівалентними, якщо вони розпізнають одну й ту саму мову.

Наприклад, знайдемо мову, яку розпізнає скінченний автомат M з діаграмою станів, зображених на рис. 38.3. Відмітимо, що дуги, які відмічені відразу двома символами (0, 1), відповідають відразу двом дугам, тобто замість двох дуг зі стану s₂ у s₂ спрямована одна, яка їх об’єднує.

---

Рис. 38.3.

Заключні стани автомата M – s₀ та s₃. Стан s₀ переводить у самого себе порожній ланцюжок , а також ланцюжки з довільної кількість нулів 0, 00, 000, … Ланцюжки, які переводять стан s₀ у s₃, складаються з якоїсь кількості нулів, після яких є 10 і довільний ланцюжок  з нулів і одиниць. Отже, L(M) = {0ⁿ, 0ⁿ10 | n = 0, 1, 2,…;  – довільний ланцюжок}.

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

Означення 38.6. Недетермінованим скінченним автоматом без виходу називають систему M = (S, I, f, s₀, F), у якій S  скінченна множина станів, I  скінченний вхідний алфавіт, f  функція переходів, яка кожній парі “стан  вхід” ставить у відповідність множину станів, s₀  S  початковий стан, F  S множина заключних (або приймаючих) станів.

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

Н а рис. 38.4 і в табл. 38.4 подано відповідно діаграму та таблицю станів якогось недетеремінованого автомату.

Рис. 38.4.

Стан	f
	Вхід
	0	1
s0	s0, s2	s1
s1	s3	s4
s2	-	s4
s3	s3	-
s4	s3	s3

Табл. 38.4.

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

Означення 38.7. Недетермінований скінченний автомат допускає (приймає) ланцюжок , якщо в множині станів, отриманій з початкового стану s₀ під дією ланцюжка , є заключний. Мова, яку розпізнає недетермінований скінченний автомат, – це множина всіх ланцюжків, які він допускає.

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

---

Теорема 38.1. Якщо мову L розпізнає недетермінований скінченний автомат M₀, то її розпізнає також детермінований скінченний автомат M₁.

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

38.3. Подання мов

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

Означення 38.8. Нехай A та B – підмножини множини V*, де V  алфавіт. Конкатенацією множин A та B (позначають AB) називають множину всіх ланцюжків , де   ланцюжок із множини A, а   ланцюжком із множини B.

Наприклад, нехай A = {0, 11} і B = {1, 10, 110}. Знайдемо множини AB та BA. Множина AB містить усі конкатенації ланцюжка з A та ланцюжка з B, тому

AB = {01, 010, 0110, 111, 1110, 11110}.

Множина BA містить усі конкатенації ланцюжка з B та ланцюжка з A:

BA = {10, 111, 100, 1011, 1100, 11011}.

Загалом AB  BA.

Використавши означення конкатенації двох множин ланцюжків, можна означити степінь множини ланцюжків Aⁿ для n = 0, 1, 2, ... . Це роблять за допомогою рекурсії:

A⁰ = {};

Aⁿ⁺¹ = AⁿA для n = 0, 1, 2,…

Нехай А = {1, 00}. Знайдемо Aⁿ для n = 1, 2, 3. A⁰ = {}, A¹ = A⁰A = {1, 00}. Щоб знайти A², візьмемо конкатенацію всіх пар елементів з A: A² = {11, 100, 001, 000}. Для відшукання A³ потрібно взяти конкатенації елементів з A² й A:

A³ = {111, 1100, 1001, 10000, 0011, 00100, 00001, 000000}.

Означення 38.9. Нехай A – підмножина множини V*. Замиканням Кліні множини A (позначають A*) називають множину всіх ланцюжків, які можна утворити конкатенацією довільної кількості ланцюжків з A. Отже,

.

Скінченні автомати можна використовувати для подання (розпізнавання) мов (множин ланцюжків). Які саме множини розпізнаються ними? Цю проблему вперше розв'язав американський математик Кліні в 1956 р. Він довів, що існує скінченний автомат, який розпізнає множину ланцюжків тоді й лише тоді, коли її можна побудувати з порожньої множини (що не містить жодного ланцюжка), множини, що містить тільки порожній ланцюжок, і множин, що містять один односимвольний ланцюжок, за допомогою операцій конкатенації, об'єднання та замикання Кліні в довільному порядку. Множини ланцюжків, які можна побудувати таким способом, називають регулярними. Регулярний вираз над множиною I рекурсивно означають так:

• символ   регулярний вираз;

• символ   регулярний вираз;

• символ x – регулярний вираз, якщо xI;

• вирази (AB), (AB) й A* регулярні, якщо вирази A та B регулярні.

Кожний регулярний вираз задає множину ланцюжків, визначену за такими правилами:

•   порожню множину, тобто таку, що не містить жодного ланцюжка;

•   множину {}, що містить тільки порожній ланцюжок;

• x – множину {x}, яка має один ланцюжок, що складається з одного символу x;

• (AB) – конкатенацію множин, поданих виразами A та B;

• (AB) – об'єднання множин, поданих виразами A та B;

• A* – замикання Кліні множини, поданої виразом A.

---

Смотрите также файлы

• dinamika.docx

• dinamika_1.docx

• komivoyazhera.docx

• Lektsiya8.doc

• M51_21_-_kopia.pdf