Утверждение: Для любого автомата Мили существует неотличимый от него автомат Мура .
Доказательство:
А)Пусть задан автомат Мили такой что:

В)Определим автомат Мура
а) , где
соответствует упорядоченным парам таким что
б) Определим функцию переходов автомата Мура:
где такова, что
в) Функция ошибки — неопределенна, можно принимать любые значения .
г) начальное состояние автомата Мура т.е. , если начальное состояние автомата Мили — .
С) Покажем, что эти автоматы неотличимы, т.е. . Для доказательства используем индукцию по длине строки
Шаг 1: базис индукции: пусть длина строки тогда
Шаг р: предположим, что где длина строки ,пусть .
Шаг р+1: очевидно, что
Вывод: результат обработки этих строк – одинаков.
Пример: Задан автомат Мили. Построить неотличимый от него автомат Мура.
A\Q q1 q2 q3
a1 q2/a q3/c q1/b
a2 q1/b q2/a q2/a

Строим неотличимый от него автомат Мура ,

A\Q q10/- q20/- q30/- q11/a q12/b q21/c q22/a q31/b q32/a
a1 q11 q21 q31 q21 q11 q31 q21 q11 q21
a2 q12 q22 q32 q22 q12 q32 q22 q12 q22
Минимизируем полученный автомат Мура

Рисуем итоговую таблицу
A\Qm C1/b C2/a C3/c
a1 C2 C3 C1
a2 C1 C2 C2