Эквивалентные автоматы

2.1. Реакция автомата

Реакцией автомата называется последовательность выходных сигналов автомата, полученная под воздействием некоторой последовательности входных сигналов, то есть реакция - это выходное слово автомата на конкретное входное слово.

Так для автомата на рис.2.1 формирование реакции представлено в табл.2.1. На вход автомата подается последовательность входных сигналов $$(z_1, z_2, z_1, z_2, z_2)$$. Автомат в исходном состоянии находится в состоянии $$A_1$$. Поступающий входной сигнал $$z_1$$ переводит автомат в состояние $$A_2$$, причем на этом переходе в тот же самый дискретный момент времени формируется выходной сигнал $$w_3$$. Во второй момент времени $$t_2$$ на автомат действует входной сигнал $$z_2,$$ который переводит автомат в состояние $$A_3$$, причем на этом переходе в тот же самый дискретный момент времени $$t_2$$ формируется выходной сигнал $$w_1$$ и так далее. В результате на входное слово $$\xi= (z_1, z_2, z_1, z_2, z_2)$$ сформировано выходное слово $$( w_3, w_1, w_1, w_2, w_2)$$, которое и является реакцией автомата.

Для автомата Мура формирование реакции происходит аналогично, с той лишь разницей, что в автомате Мура выходной сигнал выдается не на переходе автомата из состояния $$A_m$$ в состояние $$A_s$$ как в автомате Мили, а после того, как автомат перешел в состояние $$A_s$$.

2.2 Эквивалентные автоматы

Автомат Мили $$S1$$ на рис.2.2 установлен в исходное состояние $$a1$$.На вход подается входное слово: $$\xi =(z_1,z_1,z_2,z_1,z_2,z_2)$$. В результате сформировано выходное слово $$(w_1, w_2, w_1, w_1, w_1, w_2)$$, которое является реакцией автомата (табл.2.2). Автомат Мура $$S2$$ граф, которого представлен рис.2.3, установлен в исходное состояние $$a1$$.

На вход подается такое же входное слово: $$\xi=(z_1,z_1,z_2,z_1,z_2,z_2)$$. В результате сформировано выходное слово $$( w_1, w_2, w_1, w_1, w_1, w_2)$$, которое является реакцией автомата (табл.2.3).

Два автомата $$S1$$ и $$S2$$ называются эквивалентными, если:

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

2.3 Преобразование автоматов Мура в эквивалентные автоматы Мили

При табличном задании таблица переходов автомата Мили совпадает с таблицей переходов автомата Мура. Таблица выходов автомата Мили получается из таблицы переходов заменой символа $$A_s$$, стоящего на пересечении строки $$z_f$$ и столбца $$A_m$$, на символ $$w_g$$, отмечающий столбец $$A_s$$ в совмещенной таблице автомата Мура.

Пусть задан автомат Мура (табл.2.4). Таблица переходов эквивалентного автомата Мили (табл.2.5) совпадает с совмещенной таблицей автомата Мура, представляющей переходы автомата, а таблица выходов 2.6 получена следующим образом. Считается, что на переходе из состояния $$A_m$$ в состояние $$A_s$$ в эквивалентном автомате Мили должен быть сформирован такой же выходной сигнал, что и в автомате Мура, после того как автомат перешел в состояние $$а_s$$, то есть выходной сигнал $$w_g$$.

Рассмотрим переход автомата из состояния $$а1$$ в состояние $$а2$$. В автомате Мура состоянию $$а2$$ соответствует выходной сигнал $$w2$$, следовательно в табл.2.6 на переходе из состояния $$а1$$ по входному сигналу $$z1$$ ставим $$w2$$ и так далее.

При графическом задании автомата Мура переход к автомату Мили выполняется следующим образом: выходной сигнал $$w_g$$, формируемый в состоянии $$A_s$$, переносится на все дуги, входящие в эту вершину, графическая интерпретация этого показана на рис.2.4, а пример трансформации автомата Мура в эквивалентный автомат Мили показан на рис.2.5.

2.4 Преобразование автоматов Мили в эквивалентные автоматы Мура

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

В автомате Мура выходной сигнал $$w_i$$ формируется как функция $$w_i= \lambda (a_s)$$, а в автомате Мили - $$w_i=\lambda(a_m,z_f)$$. Причём $$A_s$$ - текущее состояние автомата, $$A_m$$ - предыдущее состояние автомата. Таким образом, состояние $$A_m$$ соответствует группе $$\lbrace a_s \rbrace$$, число которых равно количеству различных выходных сигналов $$\lbrace w_i \rbrace$$, расположенных на входящих дугах. Графическая интерпретация этого показана на рис.2.7.

Пусть дан автомат Мили: $$S_A=(A_A, Z_A, W_A, \delta_A, \lambda_A, a1_A)$$. Требуется перейти к эквивалентному автомату Мура $$S_В$$, то есть требуется построить такой автомат Мура : $$S_B=(A_B, Z_B, W_B, \delta_B, \lambda_B, a1_B)$$, что $$Z_B=Z_A$$ и $$W_B=W_A$$. Рассмотрим пример. Дан автомат Мили рис.2.8-2.9. Построим множество состояний автомата $$A_B$$. Для этого находим пары:

$$A_1=\{a_1/w_1, a_1/w_2\}=\{b_1, b_2\}$$ ;

$$A_2=\{a_2/w_1\}=b_3$$ ;

$$A_3=\{a_3/w_2, a_3/w_1\}=\{b_5, b_4\}$$ ;

$$A_B=\{b_1, b_2, b_3, b_4, b_5\}$$.

Переобозначив $$b_i$$ соответственно как $$A_i$$, получим граф, изображённый на рис.2.8-2.9.

(рис 2.8)

(рис 2.9)