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

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

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

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

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

Таблиця 18.1

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

Функція виходів автомата Мілі l:S ´ X ® Y.

Таблиця 18.2

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

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

Приклад. Функція переходів-виходів автомата Мура d:S´X®S; l: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

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

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

Функція переходів автомата Мілі d:S´X®S.

Таблиця 18.4

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

Функція виходів l: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