Эквивалентность автоматов Мили и Мура

Два автомата, у которых входные и выходные алфавиты совпадают или равнозначны, называют эквивалентными, если любое входное слово оба автомата перерабатывают в совпадающие выходные слова, при условии что перед началом работы оба автомата находились в начальном состоянии.

 

Построение автомата Мили эквивалентного заданному автомату Мура.

Пусть задан автомат Мура: A^o = <P^o, S^o, s₀^o, φ^o, W^o, ψ^o>.

Найти автомат Мили: A = <P, S, s₀, φ, W, ψ>.

Из определения эквивалентности следует: P = P^o, W = W^o, s₀ = s₀^o.

Как в автомате Мура, так и в автомате Мили следующие состояние зависит от текущего состояния и текущего входного символа:

в автомате Мура - s_k^o (t+1) = φ^o(s_i^o(t), p_j^o(t));

в автомате Мили - s_k (t+1) = φ (s_i (t), p_j (t)).

Из этого следует что. функция перехода автомата Мили совпадает с функцией перехода автомата Мура при одном и том - же входном символе. При этом число состояний и функций переходов не изменится т.е.:

S = S^o и φ (s_i,p_j) = φ^o(s_i^o,p_j^о).

В автомате Мили выходной символ w_k(t+1) определяется текущим состоянием s_i(t) и входным символом p_j(t):

w_k(t+1) = ψ(s_i(t), p_j(t))

В автомате Мура выходной символ w_k^o(t+1) определяется следующим состоянием s_k^o(t+1):

w_k^о(t+1) = ψ^o(s_k^o (t+1)), а это состояние: s_k^o(t+1) = φ^o (s_i^o(t), p_j^o(t))

Если подставить это выражение для s^o(t+1) в функцию выхода автомата Мура получим его определение через старое состояние:

w_k^о(t+1) = ψ^o(s_k^o (t+1)) = ψ^o(φ^o(s_i^o (t), p_j^o(t)), а так как φ (s_i,p_j) = φ^o(s_i^o,p_j^о), то для обеспечения условий эквивалентности необходимо выходные символы автомата Мили, получаемые на переходах в новые состояния сделать равными выходным символам автомата Мура этих состояний и в результате получаем: w_k(t+1) = ψ(s_i(t), p_j(t)).

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

Например, пусть задан граф автомата Мура (рис.2.10).

siо/*

s2о/w1о

s1о/w2оо

p2о

p1о

p1о

p2о

p2о

 

Рис.2.10

После переноса выходного символа из каждой вершины на каждую дугу, входящую в эту вершину, получим граф автомата Мили (рис.2.11).

s0

p2 / w2

s1

s2

p1 / w2

p2/ w1

p1 / w2

p2 / w1

 

Рис.2.11

Построение автомата Мура эквивалентного заданному автомату. Мили

Пусть задан автомат Мили: A = <P, S, s₀, φ, W, ψ>.

Найти автомат Мура: A^o = <P^o, S^o, s₀^o, φ^o, W^o, ψ^o>.

Из определения эквивалентности следует: P^o = P, W^o = W, s₀ ^o = s₀.

Как в автомате Мили, так и в автомате Мура следующие состояние зависит от текущего состояния и текущего входного символа:

в автомате Мили - s_k (t+1) = φ (s_i (t), p_j (t));

в автомате Мура - s_k^o (t+1) = φ^o(s_i^o(t), p_j^o(t)).

Из этого следует, что функция перехода автомата Мура аналогична функции перехода автомата Мили при одном и том - же входном символе. Однако так как в автомате Мура выходной символ w_k^o(t+1) определяется следующим состоянием s_k^o(t+1), то каждому состоянию может соответствовать только один выходной символ. Таким образом, если в исходном автомате Мили существуют переходы в одно и то же состояние с выдачей различных выходных символов, то в эквивалентном ему автомате Мура число состояний и соответственно число функций переходов увеличится т.е.:

[ S^o ] S ] и φ^o(s_i^o,p_j^о) φ (s_i,p_j).

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

Например, для фрагмента графа автомата Мили (рис.2.12), сделав такой перенос, получим фрагмент графа автомата Мура (рис.2.13).

si

sj

pk / wk

 

 

Рис.2.12

si/*

sj/wk pk

pk

 

 

Рис.2.13

 

 

Для фрагмента графа автомата Мили на рис.2.14 такой перенос осуществить нельзя, так как на каждом переходе происходит выдача различных выходных символов. В этом случае состояние s_m необходимо расщепить (продублировать) на такое количество состояний, сколько различных входных символов имеется на всех входных ребрах этого состояния, и сопоставить каждому из них свой выходной символ (рис.2.15).

si

sj

sk

sm

pi / wi

pj /wj Wwj

pk / wk

pi / wi

 

Рис.2.14

 

si

sm1/wi

pi

sk

sm3/wk

pk

sj

sm2/wj

pj

 

Рис.2.15

 

 

В общем случае при переходе к автомату Мура число состояний может увеличиваться и если одно и то же устройство описывается разными моделями автоматов, то в модели автомата Мура может быть больше число состояний.

Рассмотрим переход от автомата Мили, представленного ранее (рис. 2.9), к модели автомата Мура (рис. 2.16).

Автомат Мили:

p1 / w0

p2 / w0

p1 / w0

p2 / w1

p2 / w0

s0

s1

s2

p1 / w0

 

 

Автомат Мура:

 

s0/w0

p11

p1

s12/wo

s2/wo

p1

p2

s11/w1

p2

p1

p2

p21

 

Рис. 2.16

 

Состояние s₁ автомата Мили в процессе перехода было расщеплено на s₁¹ и s₁² автомата Мура. Из сравнения автомата Мура (рис. 2.9) с автоматом на рис. 2.16 видно, что это один тот же автомат, для которого ранее было проведено моделирование, и результат работы (табл. 2.5) совпадает с результатом работы автомата Мили (табл. 2.10). т.е. эти автоматы эквивалентны.

Частичные или не полностью определенные автоматы.

Пусть P = {p₀, p₁, …, p_n} – входной алфавит;

^* - множество всех слов в алфавите 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	p1/w1 s3/w1
s3	---	s0/w1	s1 s0 s0/w3

s3

s2

p3 / w1

p3/w2

p2/w1

p2/w3

p3/w3

p2/w1

 

 

Рис. 2.17

В графе частичного автомата Мили будут отсутствовать дуги, соответствующие отсутствующим переходам.