Переход от автомата Мили к автомату Мура и наоборот.

Минимизация автоматов.

Существуют различные методы минимизации. К числу простейших относится Метод Гилла, позволяющий

отыскивать классы эквивалентных состояний и заменять их отдельными состояниями.

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

и на одинаковые входные слова выдают одинаковые выходные слова (одинаковой длины).

Два состояния называются 1-эквивалентными, если они не различимы с помощью одного входного

сигнала (символа). Состояния называются k-эквивалентными, если начиная с них неразличимы входные

слова длиной в k. Если состояния k-эквивалентные для любого k, то они называются эквивалентными.

Рассмотрим минимизацию методом Гилла на каком-то конкретном автомате Мили.

Т.В.
х1	У1	У1	У1	У1	У1	У2
х2	У2	У2	У2	У2	У2	У2

Получен минимальный (с точностью до

изоморфизма) автомат, в котором классы

эквивалентных состояний заменены

именами классов. Он эквивалентен (по

поведению) исходному автомату, но имеет

три состояния вместо шести.

Замечание: Классы, в процессе их

Т.П.
х1	1/А	3/А	6/В	2/А	6/В	4/А
х2	2/А	1/А	3/А	2/А	5/А	5/А

Выделения, могут дробиться, но не

могут объединяться.

Ограниченность метода Гилла.

В полученном автомате наглядно

видно, что автомат не выйдет из

начального состояния А – оно

Т.П.
х1	1/А	3/А	6/В	2/А	6/В	4/А
х2	2/А	1/А	3/А	2/А	5/А	5/А

является тупиковым.

Следовательно, автомат никогда

не перейдет в состояния В и С,

которые в данном случае будут

недостижимыми.

 

Т.П.	А	В	С
х1	А	С	А
х2	А	В	В

 

Т.П.	А	В	С
х1	А	С	А
х2	А	В	В

Анализ тупиковых и недостиж.

состояний может повлиять

на конфигурацию миним.

автомата, либо (что скорее

 

всего) выявить ошибки в его построении. Однако метод Гилла, как и большинство других методов

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

Особенности минимизации автомата Мура

	У1	У2	У2	У2	У2	У2	У2
х1	2/B	3/B	5/B	3/B	4/B	7/B	3/B
х2	1/А	1/А	1/А	1/А	1/А	1/А	1/А

 

	y1	y2
	A	B
x1	B	B	x1

 

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

попадают состояния, отмеченные одинаковыми выходными сигналами.

 

 

Переход от автомата Мили к автомату Мура и наоборот.

Автоматы Мура и Мили отличаются функцией выходов.

y(t) = j(q(t)) – для автомата Мура

y(t) = j(q(t-1), x(t)) – для автомата Мили

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

состоит в подстановке выходных сигналов, отмечающих состояния в расширенной таблице переходов,

вместо состояний, в которые автомат переходит. Тем самым, если говорить в терминах графов, выходные

сигналы от состояний сдвигаются на стрелки, которые в эти состояния заходят.

А таблица переходов автомата Мили получается из расширенной таблицы переходов автомата Мура

отбрасыванием первой строки.

	y1	y3	y2
	A	B	C
x1	A	B	A
x2	B	B	C
x3	C	A	C

 

 

Т.П.	A	B	C
x1	A	B	A
x2	B	B	C
x3	C	A	C

 

 

Т.В.	A	B	C
x1	y1	y3	y1
x2	y3	y3	y2
x3	y2	y1	y2