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

Состояния автомата ai и aj называются эквивалентными, что обозначается как ai~aj, если для них имеет место: z

1.  (ai, z)=  (aj, z),

2.  (ai, z)~ (aj, z).

Свойства отношения эквивалентности состояний:

1. a_m ~ a_m, 2. a_m ~ a_n => a_n ~ a_m, 3. (a_m ~ a_k)&(a_n ~ a_k) a_m ~ a_n.

Таким образом, это есть отношение эквивалентности в общепринятом теоретико-множественном смысле, и множество состояний разбивается на непересекающиеся классы состояний – классы эквивалентности.

Автоматы S=<Z, W, A, , >, и S1=<Z, W, A1, 1, 1>, называют эквивалентными, что обозначается как S ~S1, если (аА а1А1, a ~ a1) &(а1А1  аА, a1 ~ a).

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

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

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

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

Рассмотрим это на примере автомата Мура Sµ=<Z,W,A, ,  ,>, где А={a0, a1, a2, a3, a4}; Z={x1,x2,x3}; W={w1,w2}. Функции автомата представлены в виде графа на рис. 1.4. Результирующий автомат функционирует в соответствии с графом на рис.1.5. Полученный автомат эквивалентен исходному автомату по построению.

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

Пусть автомат Мили S описан в виде графа на рис. 1.6. Рассмот-рим состояние a2, в которое заходят дуга (a0, a2), отмеченная выходом w1, и дуга (a3, a2), отмеченная выходом w3, и дуга (a1,a2), отмеченная выходом w2. Других заходящих дуг в эту вершину нет, значит расщепим вершину a2 в графе для автомата Мура на a2, которой сопоставим вы-ход w2 и куда направим дугу (a1, a2), вершину a1`, которой сопоставим

z2/w2

выход w1 и куда направим дугу (a0,a2`), и вершину a2``, куда направим дугу (a3,a2) и которой сопоставим выход w3. Выходные дуги для вновь введённых вершин будут те же, что и для исходной вершины. Таким образом, из вершин a2` и a2`` должны исходить дуги к тем же вершинам, что и из вершины a2.

Полученный автомат описан графом на рис. 1.7.

z2/w2

Рис.1.6

Рис.1.7

Очевидно, что автоматы S и S' эквивалентны по построению.

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