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

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

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

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

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

Рис. 2.1.

Таблица 2.1.

Моменты времени t	t1	t2	t3	t4	t5
Входные сигналы	z1	z2	z1	z2	z2
Состояния	a 1	a 2	a3	a 3	a2	a1
Выходные сигналы	w3	w1	w1	w2	w2

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

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

Автомат Мили на рис.2.2 установлен в исходное состояние .

На вход подается входное слово: .

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

Автомат Мура граф, которого представлен рис.2.3, установлен в исходное состояние .

Рис. 2.2.

Рис. 2.3.

На вход подается такое же входное слово: .

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

Таблица 2.2.

Моменты времени	t1	t2	t3	t4	t5	t6	t7
Входное слово	z1	z1	z2	z1	z2	z2
Состояния	a1	a2	a1	a1	a2	a3	a2
Выходнoе слово	w1	w2	w1	w1	w1	w2
	реакция автомата

Таблица 2.3.

Моменты времени	t1	t2	t3	t4	t5	t6	t7
Входное слово	z1	z1	z2	z1	z2	z2
Состояния	a1	a4	a2	a1	a4	a3	a5
Выходнoе слово	w1	w1	w2	w1	w1	w1	w2
	реакция автомата

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

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

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

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

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

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

Таблица 2.4.

	w1	w2	w3	w2	w3
	a1	a2	a3	a4	a5
z1	a2	a5	a5	a3	a3
z2	a4	a2	a2	a1	a1

Таблица 2.5.

	a1	a2	a3	a4	a5
z1	a2	a5	a5	a3	a3
z2	a4	a2	a2	a1	a1

Таблица 2.6.

	a1	a2	a3	a4	a5
z1	w2	w3	w3	w3	w3
z2	w2	w2	w2	w1	w1

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

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

Рис. Об этом говорит сайт https://intellect.icu . 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.

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

Из статьи мы узнали кратко, но содержательно про эквивалентные автоматы преобразование автоматов мура в мили