18.2. Способи завдання автоматів

Для завдання кінцевого автомата А необхідно задати усі компоненти вектора А = (S, X, Y, , , {s₀}), тобто вхідний Х, внутрішній S і вихідний Y алфавіти, а також функції переходів і виходів. Частіше для завдання автоматів використовуються табличний і графічний способи.

18.2.1. Табличний спосіб

Автомат Мілі задається таблицями входів і виходів

Приклад. Функція переходів автомата Мілі :SXS.

Таблиця 18.1

X	S
	s1	s2	s3
x1	S2	s3	s2
x2	S3	s2	s1

Функція виходів автомата Мілі :SXY.

Таблиця 18.2

X	S
	S1	s2	s3
x1	Y1	y3	y3
x2	Y2	y1	y1

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

Приклад. Функція переходів-виходів автомата Мура  :SXS; :SY.

Таблиця 18.3

S X	s1	s2	s3	s4	s5
Y	y1	y1	y3	y2	y3
x1	s1	s5	s5	s3	s3
x2	s4	s2	s2	s1	s1

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

Приклад Частковий автомат Мілі

Функція переходів автомата Мілі :SXS.

Таблиця 18.4

S X	s1	s2	s3	s4
x1	s2	s3	s4	-
x2	s3	-	s2	s2

Функція виходів :SXY.

Таблиця 18.5

S X	s1	s2	s3	s4
x1	y1	y3	y3	-
x2	y2	-	-	y2

Для завдання автомата Мілі часто використовують одну сполучену таблицю переходів-виходів.

Приклад. Сполучена таблиця автомата Мілі, що поєднує функції переходів і виходів

Таблиця 18.6

S X	s1	s2	s3	s4
х1	s2/y1	s3/y3	s4/y3	- / -
х2	s3/y2	- / -	s2/-	s2/y2

18.2.2. Графічний спосіб

Автомат задається у вигляді орієнтованого графу, вершини якого відповідають станам, а дуги – переходам з одного стану в інший.

Дві вершини графу s_i і s_r з'єднуються дугою, спрямованою від s_i до s_r якщо в автоматі мається перехід з s_i у s_r, тобто для деякого вхідного символу x_j s_k = (s_i, x_j). У автоматі Мілі дузі <s_i, s_k> графу приписується вхідний сигнал x_j і вихідний сигнал y_h =(s_i, x_j). Якщо автомат переходить зі стану s_i у стан s_k під дією декількох вхідних сигналів, то дузі <s_i, s_k> приписуються ці вхідні і відповідні вихідні сигнали.

При описі автомата Мура вихідний сигнал записується усередині відповідної вершини чи поруч з нею.

Приклад. Автомат Мілі з трьома станами і шістьма переходами.

Рис. 18.1. Автомат Мілі