236

Дискретна Математика :: Скінченні автомати

Тема 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 р. У цих автоматах вихід залежить лише від стану, а не від вхідного сигналу.

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