Минимизация числа состояний автомата

Теорема. Для любого автомата существует минимальный автомат с точностью до изоморфизма.

Алгоритм Мили

Пусть задан автомат S с n состояниями. На каждом шаге алгоритма будем строить некоторое разбиение множества состояний Q на классы c_ij, где i - номер шага, j - номер класса. Разбиение на i + 1 шаге получается разбиением классов, полученных на i шаге.

1. Два состояния q’ и q’’ относятся в класс c_1j, если при " a Î A для функций выхода справедливо равенство

l( q’, a ) = l( q’’, a ).

2.q’ и q’’ из класса c_ij относятся к классу c_i+1,j , если для " a Î A найдется такое j, для которого справедливы следующие отношения принадлежности

d( q’, a ) Î c_ij, d( q’’, a) Î c_ij.

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

Пример. Для автомата, заданного таблицей переходов вида:

	a₁	a₂	a₃
q₁	2,0	4,1	4,1
q₂	1,1	1,0	5,0
q₃	1,1	6,0	5,0
q₄	8,0	1,1	1,1
q₅	6,1	4,1	3,0
q₆	8,0	9,1	6,1
q₇	6,1	1,1	3,0
q₈	4,1	4,0	7,0
q₉	7,0	9,1	7,1

построить разбиение состояний на классы эквивалентности.

Решение. Построим классы c₁_j в соответствии с первым шагом алгоритма:

c₁₁= { q₁, q₄, q₆, q₉} , c₁₂= { q₂, q₃, q₈}, c₁₃={ q₅, q₇ }.

Следующие классы будем выделять в соответствии с пунктом 2 алгоритма:

c₂₁= { q₁, q₆, q₄}, c₂₂= { q₉ }, c₂₃= { q₂, q₃, q₈}, c₂₄= { q₅, q₇ };

c₃₁= { q₁, q₄ }, c₃₂= { q₆ }, c₃₃= { q₉ }, c₃₄= { q₂, q₃, q₈},

с₃₅= { q₅, q₇ }; c₄₁= { q₁, q₄ }, c₄₂= { q₆ }, c₄₃= { q₉ },

c₄₄= { q₂, q₈ }, c₄₅= { q₃ }, c₄₆= { q₅, q₇ }.

Из эквивалентных состояний, принадлежащих одному классу, оставляем только одно состояние. В итоге, множество состояний минимизированного автомата представится множеством {q₁, q₆, q₉, q₂,q₃, q₅}. Следовательно, новая таблица переходов будет иметь на три строки меньше, поскольку на три состояния уменьшилось общее число состояний заданного автомата. Таблица переходов минимального автомата будет следующей:

	a₁	a₂	a₃
q₁	2,0	1,1	1,1
q₂	1,1	1,0	5,0
q₃	1,1	6,0	5,0
q₅	6,1	1,1	3,0
q₆	2,0	9,1	6,1
q₉	5,0	9,1	5,1

Алгоритм минимизации автомата по методике Мура

1.В таблице переходов отыскиваются строки, у которых есть рабочие

состояния в одинаковых столбцах. Рабочим состоянием считается

состояние отличное от состояния ошибки. Состояния, которым

соответствуют такие строки, заносятся в группы.

2.Рабочие состояния каждой группы проверяются на эквивалентность.

3. Если среди рабочих состояний групп установлена эквивалентность, то состояния, образующие группу, считаются

эквивалентными.

Пример. Для автомата, заданного таблицей переходов вида:

	x0	x1	x2	x3	x4	x5	x6	x7
q₀	q7						q10	q_1,3
q_1,3	q2			q4
q2		q5
q4								q6
q5								q_8,19
q6								q_9,19
q7								q_9,19
q_8,19					q0	q19
q_9,19					q0	q19
q10						q11		q_14,17
q11		q12
q12						q13
q13							q19
q_14,17		q_15,18
q_15,18						q16	q19
q16							q19
q19

построить минимальный автомат, используя методику Мура.

Решение. Построим группы состояний, подозреваемых на эквивалентность, в соответствии с алгоритмом. Ими будут:

[ q₄; q₅; q₆; q₇ ] ; [ q_{8, 19}; q _{9, 19} ]; [ q₁₃; q₁₆ ]; [ q₂; q₁₁; q_14,17 ].

Состояния внутри выделенных групп необходимо проверить на эквивалентность. После проверки и удаления из групп состояний, не удовлетворяющих условию эквивалентности, классы эквивалентных состояний примут вид:

[ q5; q6; q7 ]; [ q8, 19; q 9, 19 ]; [ q13; q16 ].

Введем новые обозначения состояний автомата:

r₀= { q₅, q₆, q₇}; r₆= { q₁₀ }; r₇={ q₁₁ };

r₁= { q_9,19, q_8,19 }; r₈={ q₁₂ };

r₂= { q₁₃, q₁₆ }; r₉= { q_14,17 };

r₃= { q_1,3 }; r₁₀= { q_15,18 };

r₄= { q₂ }; r₁₁= { q₁₉ } - заключительное состояние;

r₅= { q₄ }; r₁₂= { q₀ } - начальное состояние.

Таблица переходов минимального автомата примет вид: