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

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

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

Так для автомата на рис.2.1 формирование реакции представлено в табл.2.1. На вход автомата подается последовательность входных сигналов . Автомат в исходном состоянии находится в состоянии . Поступающий входнойсигнал  переводит автомат в состояние , причем на этом переходе в тот же самый дискретный момент времени формируется выходной сигнал . Во второй момент времени  на автомат действует входной сигнал  который переводитавтомат в состояние , причем на этом переходе в тот же самый дискретный момент времени  формируется выходной сигнал  и так далее. В результате на входное слово  сформировано выходное слово , которое и является реакцией автомата.

Рис. 2.1.

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

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

Автомат Мили  на рис.2.2 установлен в исходное состояние .На вход подается входное слово: . В результате сформировано выходное слово , которое является реакцией автомата (табл.2.2). Автомат Мура  граф, которого представлен рис.2.3, установлен в исходное состояние .

Рис. 2.2.

Рис. 2.3.

На вход подается такое же входное слово: . Об этом говорит сайт https://intellect.icu . В результате сформировано выходное слово , которое является реакцией автомата (табл.2.3).

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

• входной и выходной алфавиты совпадают;
• их реакции из исходного состояния на любое входное слово совпадают;

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

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

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

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

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

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

Рис. 2.4.

Рис. 2.5.

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

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

Рис. 2.6.

В автомате Мура выходной сигнал  формируется как функция , а в автомате Мили - . Причем  - текущее состояние автомата,  - предыдущее состояние автомата. Таким образом, состояние соответствует группе , число которых равно количеству различных выходных сигналов , расположенных на входящих дугах. Графическая интерпретация этого показана на рис.2.7.

Рис. 2.7.

Пусть дан автомат Мили: . Требуется перейти к эквивалентному автомату Мура , то есть требуется построить такой автомат Мура : , что  и. Рассмотрим пример. Дан автомат Мили рис.2.8-2.9. Построим множество состояний автомата . Для этого находим пары:

 ;

 ;

 ;

.

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

Рис. 2.8.

Рис. 2.8.