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

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

Входным словом называется совокупность сигналов, поступающих на вход.

Выходным словом называются совокупность сигналов на выходе.

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

Два состояния одноэквивалентными, если на одинаковое входное слово выдается одинаковый выходной сигнал.

Два состояния k-эквивалентными, если на одинаковое входное слово длиной в k-единиц выдается одинаковый выходной сигнал длиной в k-единиц.

Эквивалентными состояниями называются k-эквивалентные состояния для любых k.

Эквивалентные состояния объединяются в класс эквивалентности.

Минимальный автомат – это автомат, состоящий из наименьшего числа состояний, каждое из которых является классом эквивалентности исходного автомата.

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

Дата добавления: 2014-01-06