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

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

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

и

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

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

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

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

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

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