Два автомата, у которых входные и выходные алфавиты совпадают или равнозначны, называют эквивалентными, если любое входное слово оба автомата перерабатывают в совпадающие выходные слова, при условии что перед началом работы оба автомата находились в начальном состоянии.
Построение автомата Мили эквивалентного заданному автомату Мура.
Пусть задан автомат Мура: Ao = <Po , So , s0o , φo , Wo , ψo>.
Найти автомат Мили: A = <P , S , s0 , φ , W , ψ>.
Из определения эквивалентности следует: P = Po, W = Wo, s0 = s0o.
Как в автомате Мура, так и в автомате Мили следующие состояние зависит от текущего состояния и текущего входного символа:
в автомате Мура - sko (t+1) = φo(sio(t) , pjo(t));
в автомате Мили - sk (t+1) = φ (si (t) , pj (t)).
Из этого следует что. функция перехода автомата Мили совпадает с функцией перехода автомата Мура при одном и том - же входном символе. При этом число состояний и функций переходов не изменится т.е. :
S = So и φ (si,pj) = φo(sio,pjо).
В автомате Мили выходной символ wk(t+1) определяется текущим состоянием si(t) и входным символом pj(t):
wk(t+1) = ψ(si(t) , pj(t))
В автомате Мура выходной символ wko(t+1) определяется следующим состоянием sko(t+1):
wkо(t+1) = ψo(sko (t+1)) , а это состояние: sko(t+1) = φo (sio(t) , pjo(t))
Если подставить это выражение для so(t+1) в функцию выхода автомата Мура получим его определение через старое состояние:
wkо(t+1) = ψo(sko (t+1)) = ψo(φo(sio (t) , pjo(t)), а так как φ (si,pj) = φo(sio,pjо), то для обеспечения условий эквивалентности необходимо выходные символы автомата Мили, получаемые на переходах в новые состояния сделать равными выходным символам автомата Мура этих состояний и в результате получаем: wk(t+1) = ψ(si(t) , pj(t)).
Преобразование автомата Мура в автомат Мили удобно производить в графическом представлении автоматов. Для этого необходимо выходные символы, которыми помечены вершины графа автомата, перенести на все дуги входящие в каждую вершину.
Например, пусть задан граф автомата Мура (рис.2.10).
Рис.2.10
После переноса выходного символа из каждой вершины на каждую дугу, входящую в эту вершину, получим граф автомата Мили (рис.2.11).
Рис.2.11
Построение автомата Мура эквивалентного заданному автомату. Мили
Пусть задан автомат Мили: A = <P , S , s0 , φ , W , ψ>.
Найти автомат Мура: Ao = <Po , So , s0o , φo , Wo , ψo>.
Из определения эквивалентности следует: Po = P, Wo = W, s0 o = s0.
Как в автомате Мили, так и в автомате Мура следующие состояние зависит от текущего состояния и текущего входного символа:
в автомате Мили - sk (t+1) = φ (si (t) , pj (t));
в автомате Мура - sko (t+1) = φo(sio(t) , pjo(t)).
Из этого следует, что функция перехода автомата Мура аналогична функции перехода автомата Мили при одном и том - же входном символе. Однако так как в автомате Мура выходной символ wko(t+1) определяется следующим состоянием sko(t+1), то каждому состоянию может соответствовать только один выходной символ. Таким образом, если в исходном автомате Мили существуют переходы в одно и то же состояние с выдачей различных выходных символов, то в эквивалентном ему автомате Мура число состояний и соответственно число функций переходов увеличится т.е.:
[ So ] 
S ] и φo(sio,pjо) 
φ (si,pj).
Преобразование автомата Мили в автомат Мура можно производить при графическом представлении автоматов. Для этого необходимо выполнить действия обратные действиям при преобразовании автомата Мура в автомат Мили т.е. выходной символ, которым помечена дуга графа автомата перенести в вершину, в которую эта дуга входит.
Например, для фрагмента графа автомата Мили (рис.2.12), сделав такой перенос, получим фрагмент графа автомата Мура (рис.2.13).
Рис.2.12
Рис.2.13
Для фрагмента графа автомата Мили на рис.2.14 такой перенос осуществить нельзя, так как на каждом переходе происходит выдача различных выходных символов. В этом случае состояние sm необходимо расщепить (продублировать) на такое количество состояний, сколько различных входных символов имеется на всех входных ребрах этого состояния, и сопоставить каждому из них свой выходной символ (рис.2.15).
Рис.2.14
Рис.2.15
В общем случае при переходе к автомату Мура число состояний может увеличиваться и если одно и то же устройство описывается разными моделями автоматов, то в модели автомата Мура может быть больше число состояний.
Рассмотрим переход от автомата Мили, представленного ранее (рис. 2.9), к модели автомата Мура (рис. 2.16).
Автомат Мили :
Автомат Мура :
Рис. 2.16
Состояние s1 автомата Мили в процессе перехода было расщеплено на s11 и s12 автомата Мура. Из сравнения автомата Мура (рис. 2.9) с автоматом на рис. 2.16 видно, что это один тот же автомат, для которого ранее было проведено моделирование, и результат работы (табл. 2.5) совпадает с результатом работы автомата Мили (табл. 2.10). т.е. эти автоматы эквивалентны.
Частичные или не полностью определенные автоматы.
Пусть P = {p0 , p1 , … , pn} – входной алфавит;
* - множество всех слов в алфавите P;
*g – множество допустимых слов ( *g 
*). Это множество входных слов, для которых определено множество выходных слов;
*z = 
\ *g - множество запрещенных слов.
Автомат называется частичным или не полностью определенным, если 
множество запрещенных слов не пусто: 
*g 
.
В таблице переходов и выхода такого автомата будут прочерки, означающие отсутствие переходов.
Пример: таблица переходов и выхода (табл. 2.11) и граф (рис. 2.17) частичного автомата Мили.
Таблица 2.11
| pj si | p1 | p2 | p3 |
| s0 | s1/w1 | --- | --- |
| s1 | --- | s2/w1 | s2/w2 |
| s2 | --- | s0/w3 | s3/w1 |
| s3 | --- | s0/w1 | s0/w3 |
Рис. 2.17
В графе частичного автомата Мили будут отсутствовать дуги, соответствующие отсутствующим переходам.
