5.2.3. Минимизация числа состояний автомата Мили методом l-эквивалентных разбиений

Два состояния автомата Мили будут 0-эквивалентными, если находящийся в этих состояниях автомат под воздействием эквивалентных входных сигналов выдает одинаковые выходные сигналы.

Два состояния a_i и a_j автомата Мили будут l‑эквивалентными, если выполняются следующие условия:

1) a_i и a_j (l–1)-эквивалентны;

2) множества классов (l–1)-эквивалентных состояний, в которые осуществляются переходы из a_i и a_j, равны между собой;

3) множества выходных сигналов, формируемых на переходах из a_i и a_j в состояния из некоторого (l–1)-го класса эквивалентности, равны между собой;

4) входные сигналы, приводящие к формированию одинакового выходного сигнала из состояний a_i и a_j, эквивалентны.

Рассмотрим пример.

Представим таблицу переходов исходного автомата Мили в следующем виде (табл. 5.21).

Таблица 5.21

Исходное состояние	Состояние перехода	Входной сигнал	Выходной сигнал	Классы
1	2 3 4 5		1 3 2 6	B1
2	6 8 6 9		5 4 5 4	B2
3	6 7		5 4	B2
4	6 8		5 4	B2
5	2 3 4 5		1 3 2 6	B1
6	2 9		3 5	B3
7	4 8		3 5	B3
8	5	1	1	B4
9	1	1	1	B4

Из таблицы видно, что произведено разбиение на 4 класса: B1, B2, B3, B4. Для проведения следующего разбиения перепишем эту таблицу в другом виде (табл. 5.22).

Таблица 5.22

Исходное состояние	Состояние перехода	Входной сигнал	Выходной сигнал	Классы
1	B2 B2 B2 B1		1 3 2 6	C1
5	B2 B2 B2 B1		1 3 2 6	C1
2	B3 B4 B3 B4		5 4 5 4	C2
3	B3 B3		5 4	C3
4	B3 B4		5 4	C2
6	B2 B4		3 5	C4
7	B2 B4		3 5	C4
8	B1	1	1	C5
9	B1	1	1	C5

В результате очередного разбиения получены 5 классов: C1, C2, C3, C4, C5. Дальнейшее разбиение невозможно, поэтому сформируем таблицу переходов минимального автомата, имеющего пять внутренних состояний (табл. 5.23).

Таблица 5.23

Исходное состояние	Состояние перехода	Входной сигнал	Выходной сигнал
1	2 3 2 1		1 3 2 6
2	4 5		5 4
3	4 4		5 4
4	2 5		3 5
5	1	1	1