8.3 Пример минимизации числа состояний автомата Мура
Шаг 1 – Автомат задан совмещенной таблицей переходов/выходов
|
0 |
1 |
y |
a0 |
a2 |
a1 |
0 |
a1 |
a3 |
a4 |
0 |
a2 |
a4 |
a3 |
0 |
a3 |
a5 |
a6 |
0 |
a4 |
a6 |
a5 |
0 |
a5 |
a2 |
a1 |
1 |
a6 |
a2 |
a1 |
0 |
Шаг 2 – Выполняется разбиение на 0-эквивалентные множества по значению выходов автомата
|
0 |
1 |
y
П0
= {A0
, A1} A0
= { a0
, a1,
a2
, a3,
a4
, a6} A1
= { a5}
* т.к.
в множестве А1 есть только одно
состояние, то состояние a5
отмечается звездочкой в таблице и не
участвует в дальнейшей минимизации,
как состояние не имеющее эквивалентных
|
a0 |
a2 |
a1 |
0 |
a1 |
a3 |
a4 |
0
А0 |
a2 |
a4 |
a3 |
0 |
a3 |
a5 |
a6 |
0 |
a4 |
a6 |
a5 |
0
А1 |
a
* |
a2 |
a1 |
1
А0 |
a6 |
a2 |
a1 |
0 |
Шаг 3 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.
|
0 |
1
П1
= {B0
, B1,
B2} B0
= { a0
, a1,
a2,
a6} B1
= { a3}
* B2
= { a4}
* т.к.
в множестве B1 и В2
есть только одно состояние, то состояние
a3 и a4
отмечаются звездочкой в таблице и не
участвуют в дальнейшей минимизации,
как состояния не имеющие эквивалентных
|
a0 |
A0 |
A
B0 |
a1 |
A0 |
A0 |
a
* |
A0 |
A
B1 |
a3 |
A1 |
A
B2 |
a
* |
A0 |
A 1 |
a
* |
a2 |
a
B0 |
a6 |
A0 |
A 0 |
5
Шаг 4 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.
|
0 |
1
П2
= {C0
, C1,
C2} C0
= { a0,
a6} C1
= { a1}
* C2
= { a2}
* т.к.
в множестве C1
и C2
есть только одно состояние, то состояние
a1 и a2
отмечаются звездочкой в таблице и не
участвуют в дальнейшей минимизации,
как состояния не имеющие эквивалентных
C0 |
a0 |
B0 |
B
C1 |
a1 |
B1 |
B
C2 |
a
*
*
* |
B2 |
B 1 |
a3 |
A1 |
A
B1 |
a
* |
A0 |
A
B2
A0 |
a
* |
a2 |
a
C0 |
a6 |
B0 |
B 0 |
Шаг 5 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.
|
0 |
1
П3 = {D0
} D0
= { a0, a6} т.к.
в множестве D0
и C0
одинаковые
состояния, а сами множества получены
на двух последовательных шагах
разбиения, то состояния a0
и a6,
которые составляют данное множество
являются полностью эквивалентными
D0 |
a
* |
C1 |
C
C1 |
a
* |
B1 |
B
C2 |
a
* |
B2 |
B1 |
a3 |
A1 |
A
B1 |
a
* |
A0 |
A
B2
A0 |
a
* |
a2 |
a
D0 |
a6 |
C1 |
C 2 |
На данном шаге минимизация окончена, т.к. выделено множество полностью эквивалентных состояний, а все остальные состояния не имеют эквивалентных т.к. они попали в множества из одного элемента.
В исходной таблице переходов/выходов цифрового автомата вычеркивается строка, которая соответствует состоянию a6, а в остальных строках a6 заменяется на a0
|
0 |
1 |
y |
a0 |
a2 |
a1 |
0 |
a1 |
a3 |
a4 |
0 |
a2 |
a4 |
a |
0 |
a 3 |
a5 |
a6 |
0 |
a4 |
a6 |
a5 |
0 |
a5 |
a2 |
a1 |
1 |
a 6 |
a2 |
a1 |
0 |
3
Таблица переходов/выходов автомата после минимизации будет иметь следующий вид:
|
0 |
1 |
y |
a0 |
a2 |
a1 |
0 |
a1 |
a3 |
a4 |
0 |
a2 |
a4 |
a3 |
0 |
a3 |
a5 |
a0 |
0 |
a4 |
A0 |
a5 |
0 |
a5 |
a2 |
a1 |
1 |