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

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

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

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

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

( q’,  ) = ( q’’,  ).

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

( q’,  )  c_ij, ( q’’, )  c_ij.

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

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

	a1	a2	a3
q1	2,0	4,1	4,1
q2	1,1	1,0	5,0
q3	1,1	6,0	5,0
q4	8,0	1,1	1,1
q5	6,1	4,1	3,0
q6	8,0	9,1	6,1
q7	6,1	1,1	3,0
q8	4,1	4,0	7,0
q9	7,0	9,1	7,1

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

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

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₅ }. Следовательно, новая таблица переходов будет иметь на три строки меньше, поскольку на три состояния уменьшилось общее число состояний заданного автомата. Таблица переходов минимального автомата будет следующей:

	a1	a2	a3
q1	2,0	1,1	1,1
q2	1,1	1,0	5,0
q3	1,1	6,0	5,0
q5	6,1	1,1	3,0
q6	2,0	9,1	6,1
q9	5,0	9,1	5,1

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

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

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

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

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

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

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

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

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

	x0	x1	x2	x3	x4	x5	x6	x7
q0	q7						q10	q1,3
q1,3	q2			q4
q2		q5
q4								q6
q5								q8,19
q6								q9,19
q7								q9,19
q8,19					q0	q19
q9,19					q0	q19
q10						q11		q14,17
q11		q12
q12						q13
q13							q19
q14,17		q15,18
q15,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₀ } - начальное состояние.

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

	x0	x1	x2	x3	x4	x5	x6	x7
r0								r1
r1					r12	r11
r2							r11
r3	r4			r5
r4		r0
r5								r0
r6						r7		r9
r7		r8
r8						r2
r9		r10
r10						r2	r11
r11
r12	r0						r6	r3