4.3 Эквивалентные состояния. Минимизация к.Д.А.

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

Определение. Два автомата называются изоморфными, если их диаграммы Мура изоморфны.

Рассмотрим два автомата   и   с одинаковыми входным и выходным алфавитами.

Определение. Состояния   и   называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого входного слова х результат работы автомата   такой же, как и для  .

В частном случае, когда  = , то речь идет о неотличимых состояниях одного автомата.

Определение. Автоматы   и   называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого состояния   найдется эквивалентное ему состояние   и обратно.

Неотличимые автоматы осуществляют одно и то же отображение входных слов в выходные.

Определение. Автомат А называется приведенным, если в нем нет эквивалентных (неразличимых) состояний.

Число состояний в приведенном автомате минимально. Для любого автомата   существует эквивалентный ему приведенный автомат А. Процедура нахождения такого автомата называется минимизацией автомата  .

4.4 Алгоритм минимизации конечного автомата.

Шаг 1: два состояния s и t относим в один класс  , если для любого входного символа x значение функции выхода sсовпадает со значениями функции выхода t. В результате получим r классов:

.



Шаг k: два состояния s и t из одного класса  , полученного на предыдущем шаге, относим в один класс  , если для любого значения входного символа значения функций состояний принадлежат одному и тому же классу из предыдущего шага. Если шаг k не изменяет разбиения, то процесс останавливается. Доопределяем функции перехода и выхода и строим таблицу переходов –выходов.

Пример. Минимизировать автомат, заданный таблицей:

Шаг 1: Первое, третье и четвертое состояния отнесем в один класс состояний, а второе, пятое и шестое – в другой:

; 

Шаг 2: Выпишем значения функции переходов для состояний из класса  :

;  ; 

;  ; 

;  ; 

Видно, что 1 и 3-е состояния относим в один класс этого шага  , а четвертое состояние – в другой  . Проанализировав аналогичным образом значения функции выходов для состояний из класса  , видим:

;  ; 

;  ; 

;  ;  , т.е. все они остаются в одном классе. В результате получим разбиение на классы:

;  ; 

Шаг 3:  ;  ;  . Дальнейшего разбиения классов не происходит, поэтому процесс останавливается. Класс   назовем состоянием  , класс состояний   назовем состоянием  , а класс   – состоянием  .

Построим таблицу переходов–выходов:

Построенный автомат – минимальный.

4.5 Каноническая таблица. Канонические уравнения.

Реализация К.Д.А. осуществляется на основе канонических уравнений, которые находятся с помощью канонической таблицы. Каноническая таблица строится следующим образом по таблице переходов–выходов или диаграмме Мура.

Аргументы функций  и  находятся в столбцах слева, а справа – их значения.

S\X		…		…



s(t)	x(t)	y(t)	s(t+1)
…	…	…	…
…	…	…	…
…	…	…	…
…	…	…	…

Канонические уравнения имеют вид:

Элементы множеств S, X, Y кодируют двоичными наборами, соблюдая при этом следующие условия:

1. разным элементам в каждом из множеств S, X, Y соответствуют разные кодовые наборы;

2. длины кодовых наборов в каждом из множеств S, X, Y должны совпадать и быть по возможности минимальными;

3. начальному состоянию соответствует набор  .

После кодирования  ,  ,   принимают вид:

=

=

=

Таблица преобразовывается к скалярному виду следующим образом:

	…		…		…			…
…	.	…		…		…	…		…

* Для того, чтобы представить  ,   как булевы функции, необходимо, чтобы они были всюду определены. С этой целью к таблице добавляются строки, содержащие в левой части недостающие наборы, а в правой части – прочерки. Затем, прочерки заполняются 0 и 1 (функции доопределяются) так, чтобы по соответствующим столбцам значений  и можно было записать формулу в виде СКНФ или СДНФ или в каком-нибудь другом наиболее простом виде.

Пример. Автомат задан таблицей переходов – выходов:

Записать его канонические уравнения.

Закодируем состояние  00 (начальное), состояние  01, состояние  10.

Запишем каноническую таблицу:

s(t)	x(t)	y(t)	s(t+1)
00	0	1	01
00	1	1	10
01	0	1	01
01	1	1	01
10	0	0	10
10	1	1	10

И преобразуем ее к скалярному виду:

(t)	(t)	x(t)	y(t)	(t+1)	(t+1)
0	0	0	1	0	1
0	0	1	1	1	0
0	1	0	1	0	1
0	1	1	1	0	1
1	0	0	0	1	0
1	0	1	1	1	0

Две последние строки доопределим следующим образом:

(t)	(t)	x(t)	y(t)	(t+1)	(t+1)
0	0	0	1	0	1
0	0	1	1	1	0
0	1	0	1	0	1
0	1	1	1	0	1
1	0	0	0	1	0
1	0	1	1	1	0
1	1	0	1	0	0
1	1	1	1	0	0

Запишем канонические уравнения:

.

Осталось упростить уравнения.

Применим метод группировки 

= ;

= ;

и запишем канонические уравнения в более простом виде: