Алгоритм минимизации автомата Мили

1. По таблице выхода находятся состояния с одинаковыми выходными сигналами. Данные состояния объединяются в класс одноэквивалентных состояний. Проводится перекодировка.

2. По таблице перехода определяются классы двухэквивалентных состояний: для любого класса выделяется состояние, которое на одинаковый входной сигнал переходит в одинаковое состояние. Объединяем двухэквивалентные состояния в классы двухэквивалентных состояний. Проводится перекодировка.

3. Алгоритм выполняется, пока в классах k-эквивалентных состояний не находятся одинаковые состояния.

4. Вводятся новые состояния, соответствующие классам эквивалентных состояний.

5. С учетом новых состояний переписываются таблицы перехода и выхода.

 

ПРИМЕР

Пусть задан автомат Мили

Таблица выходов

 

Таблица переходов

 

 

Определяем класс одноэквивалентных состояний по таблице выхода

Таблица выходов

	а	в	а	в	а	в	а	в

 

Выделяются два класса одноэквивалентных состояний a ={1,3,5,7,8} и b ={2,4,6,9}. Перегруппируем таблицу перехода по классам одноэквивалентных состояний

Таблица переходов

	а	в

 

Перекодируем состояния по полученным классам

Таблица переходов

	а	в
	2/в	2/в	6/в	6/в	4/в	1/а	3/а	8/а	7/а
	2/в	2/в	4/в	2/в	4/в	4/в	2/в	9/в	9/в
	5/а	5/а	3/а	8/а	7/а	4/в	2/в	6/в	7/а

Выделяем внутри каждого из классов одинаковые состояния, тем самым определяя классы двухэквивалентных состояний

Таблица переходов

	а	в
	2/в	2/в	6/в	6/в	4/в	1/а	3/а	8/а	7/а
	2/в	2/в	4/в	2/в	4/в	4/в	2/в	9/в	9/в
	5/а	5/а	3/а	8/а	7/а	4/в	2/в	6/в	7/а
	а	в	с

Определим новые классы двухэквивалентных состояний a ={1,3,5,7,8}, b ={2,4,6}, c ={9}, перекодируем по новым состояниям и выделим классы трехэквивалентных состояний

Таблица переходов

	а	в	с
	2/в	2/в	6/в	6/в	4/в	1/а	3/а	8/а	7/а
	2/в	2/в	4/в	2/в	4/в	4/в	2/в	9/с	9/с
	5/а	5/а	3/а	8/а	7/а	4/в	2/в	6/в	7/а
	а	в	с	d

Классы трехэквивалентных состояний a ={1,3,5,7,8}, b ={2,4}, c ={6}, d ={9} перекодируем по новым состояниям и выделим классы четырехэквивалентных состояний

Таблица переходов

	а	в	с	d
	2/в	2/в	6/с	6/с	4/в	1/а	3/а	8/а	7/а
	2/в	2/в	4/в	2/в	4/в	4/в	2/в	9/d	9/d
	5/а	5/а	3/а	8/а	7/а	4/в	2/в	6/с	7/а
	а	в	а	c	d	e

Перегруппируем таблицу перехода по новым классам a ={1,3,8}, b ={5,7}, c ={2,4}, d ={6}, е ={9}, перекодируем по новым состояниям.

Таблица переходов

	а	в	c	d	e
	2/с	2/с	4/с	6/d	6/ d	1/a	3/a	8/a	7/b
	2/с	2/с	4/с	4/c	2/c	4/c	2/c	9/e	9/e
	5/в	5/в	7/в	3/a	8/a	4/c	2/c	6/d	7/b
	а	в	c	d	e

Так как внутри из каждого класса дальнейшее разбиение на классы не осуществляется, это означает, что найдены классы эквивалентных состояний :. a ={1,3,8}, b ={5,7}, c ={2,4}, d ={6}, е ={9}.

Минимизированный автомат Мили в новых состояниях имеет вид

Таблица переходов

 

	a	b	c	d	e
	с	d	a	a	b
	с	c	c	e	e
	в	c	c	d	b

 

Таблица выходов

 

	a	b	c	d	e
	1	1	0	0	0
	0	0	1	0	0
	0	0	1	1	1

 

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

:

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

 

Минимизация частичных автоматов.

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