Графический способ
Табличный способ
При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.
Таблица переходов
xj\ai | a0 | … | an |
x1 | d(a0,x1) | … | d(an,x1) |
… | … | … | … |
xm | d(a0,xm) | … | d(an,xm) |
Таблица выходов
xj\ai | a0 | … | an |
x1 | l(a0, x1) | … | l(an, x1) |
… | … | … | … |
xm | l(a0, xm) | … | l(an, xm) |
Строки этих таблиц соответствуют входным сигналам x (t), а столбцы – состояниям. На пересечении столбца ai и строки x j в таблице переходов ставится состояние a s = d [ a i, x j], в которые автомат перейдет из состояния a i под воздействием сигнала x j; а в таблице выходов – соответствующий этому переходу выходной сигнал y g = l [ a i, x j]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов, она в некоторых случаях более удобна.
Совмещенная таблица переходов и выходов автомата Мили.
xj\ai | a0 | … | an |
x1 | d(a0,x1)/ l(a0,x1) | … | d(an,x1)/ l(an,x1) |
… | … | … | … |
xm | d(a0,xm)/ l(a0,xm) | … | d(an,xm)/ l(an,xm) |
Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но также и все три алфавита: входной, выходной и алфавит состояний. Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется только одна таблица, которая называется отмеченной таблицей переходов автомата Мура.
Отмеченная таблица переходов автомата Мура
yg | l(a0) | … | l(an) |
xj\ac | a0 | … | an |
x1 | d(a0,x1) | … | d(an,x1) |
… | … | … | … |
xm | d(a0,xm) | … | d(an,xm) |
В этой таблице каждому столбцу приписан, кроме состояния a i, еще и выходной сигнал y (t) = l (a (t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом. Примеры табличного задания автоматов Мили и Мура.
Автомат Мура:
yg | y2 | y1 | y1 | y3 | y2 |
xj\xj | a0 | a1 | a2 | a3 | a4 |
x1 | a2 | a1 | a3 | a4 | a2 |
x2 | a3 | a4 | a4 | a0 | a1 |
Автомат Мили:
xj\ai | a0 | a1 | a2 | a3 |
x1 | a1/y1 | a2/y3 | a3/y2 | a0/y1 |
x2 | a0/y2 | a0/y1 | a3/y1 | a2/y3 |
По этим таблицам можно найти реакцию автомата на любое входное слово.
Для автомата Мура: | ||||||
x1 | x2 | x2 | x2 | x1 | … | |
a0 | a2 | a4 | a1 | a4 | ||
y2 | y1 | y2 | y1 | y2 | ||
Для автомата Мили: | ||||||
x1 | x2 | x2 | x2 | x1 | … | |
a0 | a1 | a0 | a0 | a0 | a1 | |
y1 | y1 | y2 | y2 | y1 |
При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s, если в автомате имеется переход из a i в a s, то есть a s = d (a i, x j). В автомате Мили дуга отмечается входным сигналом x j, вызвавшим переход, и выходным сигналом y g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.