Теорема

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

Автоматы Мили и Мура.

Эквивалентность автоматов.

Определение:

Два состояния a_i и a _j называются эквивалентными, и обозначаются как a_i~a_j, если l(a_i,z_k)=l(a_j,z_k) для любого слова, то есть реакция автомата в этих состояниях на любые слова одинакова.

Определение:

Два автомата S=<Z,W,A,l,d> и S'=<Z,W,A',l',d'> называются эквивалентными, то есть S~S', если для любого a_i из A существует a_j из A' такое, что a_i~a_j, и если для любого a_j из A' существует a_i из A такое, что a_j~a_i.

Oпределение: Состояния называются k-эквивалентными, если реакция этих состояниях на слова длины k одинакова.

Отношение эквивалентности состояний есть отношение бинарной эквивалентности:

a_i~a_j Þ a_i~ a_j,

a_i~a_k & a_j~a_k Þ a_i~a_j.

На практике наибольшее распространение получили два класса автоматов - автоматы Мили и Мура. Закон функционирования автомата Мили задается уравнениями:

a(t+1)=d(a(t),z(t)); w(t)=l(a(t),z(t)), t=0,1,2...

Автоматами Мура называют автоматы, у которых выход зависит только от состояния, и не зависит от значения входа:

a(t+1)=d(a(t),z(t)); w(t)=l(a(t)), t=0,1,2...

Введем понятие слова в любом из алфавитов как последовательность символов данного алфавита. Если предположить, что на входе автомата в состоянии а_i задано некоторое слово Z=z1z2z3, то по функциям l и d можно определить слово состояний и слово выходов, соответствующих этим входному слову и состоянию. Последнюю букву выходного слова при этом называют реакцией автомата в состоянии а_i на слово Z.

Введены две модели автоматов:

автомат Мура

автомат Мили

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

Для любого автомата Мура существует эквивалентный автомат Мили и наоборот.

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

Необходимость: Докажем, что для любого(полностью определенного) автомата Мура существует эквивалентный ему автомат Мили.

Рассмотрим автомат Мура:

Sµ=<X,Y,A,d, m,a§A>, где

А={a1,a2,a3,a4};

X={x1,x2,x3};

Y={y1,y2};

описанный в виде графа

Перенесем выходы автомата с вершин графа на входящие ветви графа.

Получаем граф, который описывает автомат

S'=<X',Y',A',d',l,a§A'>, где

A'=А={a0,a1,a2,a3,a4};

X'=X={x1,x2,x3};

Y'=Y={y1,y2};

Автомат S' эквивалентен автомату S, т.к для любого состояния a1§ A aавтомата S существует состояние a1§ A' автомата S' такое, что реакции автоматов на любые слова в этих состояниях одинаковы, и наоборот.

Достаточность:

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

Рассмотрим автомат Мили

S=<X,Y,A,d,l,a0§A'>, где

А={a0,a1,a2,a3};

X={x1,x2};

Y={y1,y2,y3};

описанный в виде графа

Таким образом получим граф, который описывает автомат

S=<X',Y',A',d,m,a0§A'>, где

A'=А={a0,a1',a2',a2'',a2''',a3',a3''};

X'=X={x1,x2};

Y'=Y={y1,y2,y3};

Докажем, что автоматы S и S' эквивалентны. Для этого докажем, что для любого состояния ai§A автомата S существует эквивалентное ему состояние ai§A' автомата S' и наоборот.

Покажем, что для любого состояния множества {a0,a1,a2,a3} существует эквивалентное из множества {a0,a1',a2',a2'',a2''',a3',a3''};

a0~a0'