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

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

Минимизация автомата Мура отличается первым шагом. Здесь в классы одно-эквивалентных попадают состояния, отмеченные одинаковыми выходными сигналами.

А В

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

y(t) = j(q(t)) – для автомата Мура

и

y(t) = j(q(t-1), x(t)) – для автомата Мили

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

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

	y1	y3	y2
x2 A	A	B	C
x1	A	B	A
x1 x1 x3 B x2	B	B	C
x3 x3	C	A	C

Теорема : (Глушкова)

Таким образом доказана конструктивная теорема, что для произвольного автомата Милли может быть построен эквивалентный ему автомат Мура имеющий не более

n * m + 1 состояний, где n - число входных сигналов, m - число состояний исходного автомата Милли.