Эквивалентные автоматы
Два автомата Sa и Sb с одинаковыми входными и выходными алфавитами называются эквивалентными. Для любого автомата Мили существует эквивалентный ему автомат Мура, и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили.
Автомат Мили (англ. Mealy machine) — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В в вершины графа автомата Мили записываются выходящие сигналы,а дугам графа приписывают условие перехода из одного состояния в другое,а также входящие сигналы. Автомат Мили можно описать пятеркой (Q,X,Y,f,g), где Q - множество состояний автомата, X - множество входных символов, Y - множество выходных символов, q=f(Q,X) - функция состояний, y=g(Q,Y) - функция выходных символов. Кодировка автомата Мили: Вершина (операторная или логическая),стоящая после вершины "Начало" ,а также вход вершины "Конец" помечается символом S1,вершины,стоящие после операторных помечаются символом Sn (n=2,3..).
Автомат Мура
Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура. В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе.
Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов:
где S, X, Y и δ — соответствуют определению автомата типа Мили, а μ является отображением вида: μ : S → Y,
с зависимостью состояний и выходных сигналов во времени уравнением:
.

Особенностью автомата Мура является то, что символ y(t) в выходном канале существует все время пока автомат находится в состоянии s(t).
Для любого автомата Мура существует автомат Мили, реализующий ту же самую функцию. И наоборот: для любого автомата Мили существует соответствующий автомат Мура.

    Пусть , i = 1, 2 – автоматы с одинаковыми входными и выходными алфавитами. Состояния автомата А1 и автомата А2 называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого слова справедливо
    .
    Отсюда следует, что при подаче на вход автоматов любого слова выходные слова автоматов, находящихся соответственно в состоянии и совпадают (состояния не различаются по выходу).
    В частности, может быть А1= А2, и речь будет идти о неотличимых состояниях одного автомата. Отношение неотличимости на множестве состояний одного автомата является отношением эквивалентности. Оно разбивает множество всех состояний на непересекающиеся классы. Каждый класс содержит все неотличимые между собой состояния.
    Автоматы А1 и А2 называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого состояния автомата А1 существует эквивалентное ему состояние автомата А2, и для каждого состояния автомата А2 существует эквивалентное ему состояние автомата А1. Неотличимые автоматы осуществляют одно и то же отображение входных слов в выходные.