2015-06-28
287
Для завдання кінцевого автомата А необхідно задати усі компоненти вектора А = (S, X, Y, d, l, {s0}), тобто вхідний Х, внутрішній 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 |
Автомат Мура описується однією (відзначеною) таблицею переходів, у якій для кожного стовпця, крім стану si є визначеним ще і вихідний сигнал yh =l(si).
Приклад. Функція переходів-виходів автомата Мура 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 |
