Переход от автомата Мили к автомату Мура

Минимизация частичных автоматов.

Особенности минимизации автомата Мура.

:

Автомат Мура минимизируется аналогично минимизации автомата Мили за исключением первого шага. Выделение класса одноэквивалентных состояний осуществляется по строке выходов отмеченной таблицы переходов автомата Мура.

Для того, чтобы провести минимизацию частичных автоматов неопределенное состояние доопределяется самостоятельно. Далее минимизация автоматов осуществляется по вышеизложенному алгоритму.

Автоматы Мили и автоматы Мура отличаются функцией выхода.

Автомат Мили:

(5.5)

Автомат Мура:

(5.6)

То есть произвольному состоянию автомата Мили и входному сигналу соответствует состояние автомата Мура:

(5.7)

При этом начальные состояния автоматов Мили и Мура совпадают:

(5.8)

Учитывая вышеизложенное, можно перекодировать таблицу перехода автомата Мили и составить отмеченную таблицу переходов автомата Мура.

ПРИМЕР

Пусть задан автомат Мили

Таблица переходов (ТП) Таблица выходов (ТВ)

Перекодируем матрицу перехода автомата Мили:

	/	/	/
	/	/	/

Составляем таблицу перехода автомата Мура.

При составлении таблицы перехода автомата Мили рассуждаем следующим образом: состояние автомата Мура соответствует состоянию автомата Мили , следовательно, столбец состояния автомата Мура совпадает со столбцом состояния автомата Мили.

Так как в автомате Мура произвольному состоянию соответствует некоторый выходной сигнал, то строка выхода отмеченной таблицы перехода автомата Мура однозначно определяется таблицей выхода автомата Мили (состоянию соответствует выходной сигнал ; - )

Выходной сигнал, соответствующий состоянию , выбирается произвольно.

Если автомат Мили содержит m -состояний и n входных символов, то количество состояний автомата Мура определяется по формуле:

(5.9)