Эквивалентные автоматы. Эквивалентные преобразования автоматов

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

При описании алгоритмов взаимной трансформации автоматов Мили и Мура в соответствии с изложенным выше мы будем пренебрегать в автоматах Мура выходным сигналом, связанным с начальным состоянием ( (a₁)).

Рассмотрим сначала преобразование автомата Мура в автомат Мили.

Пусть дан автомат Мура: S_A={ Х_A, А_A, У_A,_A,_A, а_оA}, где:

Х_A={х₁, х₂,. х_n}; Y={y₁, у₂,. у_m}; А={ а₀, а₁, а₂,. а_N}; а_0A = а_{0 -} начальное состояние (а_0A А); _A - функция переходов автомата, задающая отображение (Х_AхА_A) - >А_A; _A - функция выходов автомата, задающая отображение А_A->У_A.

Построим автомат Мили: S_B={ Х_B, А_B, Y_B,_B, _B, а_0B}, у которого А_B=А_A; Х_B=Х_A; Y_B=У_A; _B=_A; а_0B=а_0A. Функцию выходов _B определим следующим образом. Если в автомате Мура _A (а_m, х₁) = а_s и _A (а_s) =y_g, то в автомате Мили _B (a_m, х₁) =y_g

Рисунок 1.7 - Иллюстрация перехода от модели Мура к модели Мили

Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал y_g записанный рядом с вершиной (a_s), переносится на все дуги, входящие в эту вершину.

При табличном способе задания автомата таблица переходов автомата Мили совпадает с таблицей переходов исходного автомата Мура, а таблица выходов получается из таблицы переходов заменой символа a_s, стоящего на пересечении строки х_f и столбца а_m, символом выходного сигнала y_g отмечающего столбец a_s в таблице переходов автомата S_A.

Из самого способа построения автомата Мили S_B очевидно, что он эквивалентен автомату Мура S_A. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов S_A и S_B, установленных в состояния a_m, вызовет появление одинаковых выходных слов и, следовательно, автоматы S_A и S_B эквивалентны.

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

S_A={ Х_A, А_A,Y_A, _A, _A, a_0A},

где:

Х_A={x₁, x₂,. x_n}; Y={y₁, у₂,. y_m}; А={ a₀,a₁,a₂,. a_N}; a_0A = a₀ - начальное состояние (а_0A А); _A - функция переходов автомата, задающая отображение (Х_AxА_A) - >А_A; _A - функция выходов автомата, задающая отображение (Х_AxА_A) - >Y_A.

Построим автомат Мура: S_B={X_B, A_B, Y_B, _B, _B, a_0B}, у которого X_B=X_A; Y_B=Y_A.

Для определения A_B каждому состоянию a_s А_A поставим в соответствие множество A_s всевозможных пар вида (a_s, y_g)

Функцию выходов _B определим следующим образом. Каждому состоянию автомата Мура S_B, представляющему собой пару вида (a_s,y_g), поставим в соответствие выходной сигнал y_g.

Если в автомате Мили S_A был переход _A (a_m, x_f) = a_s и при этом выдавался выходной сигнал _A (a_m,x_f) =y_g, то в S_B будет переход из множества состояний A_m, порождаемых a_m, в состояние (a_s,y_g) под действием входного сигнала x_f.

В качестве начального состояния a_0B можно взять любое из состояний множества A₀, которое порождается начальным состоянием a₀ автомата S_A. При этом выходной сигнал в момент времени t=0 не должен учитываться.

Рассмотрим пример. Пусть задан автомат Мили (табл.1.10.)

Поставим в соответствие каждой паре а_i/x_k состояние Ь_ik (i-номер состояния, k-номер входного сигнала), с учетом b₀.

Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:

1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (b_ik):

а₀= {b₀, b₀₂, b₁₁, b₂₁}; a₁= {b₂₂}; а₂= {b₀₁, b₁₂};

2) Если состояние автомата Мура b_ik входит в множество, соответствующее состоянию а_p автомата Мили, то в строку таблицы переходов автомата Мура для состояния b_ik следует записать строку из таблицы переходов автомата Мили, соответствующую состоянию а_р (из 1.10.).

3) Функцию выходов автомата Мура определим следующим образом: _B (b_ik) =_A (а_i, x_k). Для начального состояния b₀ значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a₀ (с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.

4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).

Если выходной сигнал возле b₀ доопределить y₁, то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b₀,b₁₁,b₀₂). Заменив класс эквивалентности одним представителем (b₀), получим окончательную таблицу переходов (табл.1.13).

Таблица 1.12

Таблица 1.13.

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

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