Граф для автомата Мили

Графический способ

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

При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Таблица переходов

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), а столбцы – состояниям. На пересечении столбца a_i и строки 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, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.

Дата добавления: 2014-10-31