6. Минимизация автомата

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

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

Построим треугольную таблицу (табл. 6), клетки которой соответствуют всем парам рабочих состояний (q_i, q_j) i  j, т.е. состояний, отличных от q₂₀ «Ошибка». Если для рабочих состояний q_i и q_j в табл. 5 существует входной символ х₁, при котором переход из q_i осуществляется в одно из рабочих состояний, а из q_j в состояние ошибки, то состояние q_i и q_j не эквивалентны, и соответствующая им клетка помечается крестом. То есть, если какие - либо две строчки табл. 5 содержат разное число рабочих состояний или отличаются позициями, занимаемыми рабочими состояниями, то обозначающие эти строки состояния не эквивалентны. В противном случае в клетку табл. 6 с координатами q_i q_j запишем каждую пару состояний (q_s, q_t), t  s, в которые автомат может перейти из q_i и q_j при подаче одного и того же входного символа (количество этих пар равно числу столбцов с рабочими состояниями в строке q_i и q_j табл. 5).

В рассматриваемом случае в табл. 5 автомат из состояния q_o переходит в рабочие состояния при входных символах х₂ , х₃ , х₅ , при остальных входных символах q_o переходит в состояние q₂₀ «Ошибка». Других состояний, которые оказываются в рабочих состояниях при том же наборе входных символов (х₂ , х₃ , х₅) нет, поэтому в столбце q_o табл. 6 все клетки следует вычеркнуть. То же можно сделать со столбцами q_i,3, q₂, q_4. Из состояния q₅ автомат переходит в состояния q₁₉ , q₈ при входных символах х_о , x_i , и при этих же символах в рабочие состояния автомат переходит из состояний q₆ ( q₁₉ , q₉) и q₇ (то же q₁₉ , q₉). Поэтому две клетки в столбце q₅ не должны вычеркиваться и в них должны быть вписаны: в первую пару состояний (q₁₉, q₈; q₁₉, q₉), во вторую — то же (q₁₉, q₈; q₁₉, q₉). Для экономии места в клетки вписываются только индексы состояний. Такая запись означает, что состояния q₅ и q₆ (q₅ и q₇) будут эквивалентны, если эквивалентны состояния q₁₉, q₈ и q₁₉, q₉. Из состояний q₆ и q₇ автомат переходит при х_о в состояния q₁₉ ,q₉. Аналогично, из q₈ и q₉ автомат переходит при x₆ в q_o, а при х₇ - в q₁₉.

В этом случае пары состояний q₅ и q₆, q₆ и q₇, q₅ и q₇, q₈ и q₉ являются явно эквивалентными, как и пары q₁₃ и q₁₆ , q₁₃ и q₁₈ , q₁₆ и q₁₈. В табл. 6 таким состояниям соответствуют непомеченные клетки. Таким образом заполняются все клетки табл. 6.

Затем в табл. 6 следует вычеркнуть клетки, в которых записаны индексы хотя бы одного состояния, помечающего строку и столбец со всеми вычеркнутыми состояниями. По этому правилу зачеркиваются ранее заполненные клетки в столбце 17, затем снова необходимо вычеркнуть все клетки, которые содержат индексы состояний с вычеркнутыми клетками и т. д. пока не образуется таблица, в которой ни одной клетки вычеркнуть уже нельзя. В нашем случае необходимо вычеркнуть клетки в строке 17, столбцах 13 и 16, остальные клетки вычеркнуть нельзя.

Таблица 6

1,3

X

2

X

X

(19,8; 19,9)

4

X

X

X

5

X

X

X

X

6

X

X

X

X

7

X

X

X

X

8

X

X

X

X

X

X

X

9

X

X

X

X

X

X

X

10

X

X

X

X

X

X

X

X

X

(12; 15)

11

X

X

X

X

X

X

X

X

X

X

(13; 16)

12

X

X

X

X

X

X

X

X

X

X

X

(19; 18)

13

X

X

X

X

X

X

X

X

X

X

X

X

(19; 18)

14

X

X

X

X

X

X

X

X

X

X

X

X

15

X

X

X

X

X

X

X

X

X

X

X

X

X

(19; 18)

16

X

X

X

X

X

X

X

X

X

X

X

X

X

X

17

X

X

X

X

X

X

X

X

X

X

X

X

X

X

18

X

X

X

X

X

X

X

X

X

X

X

X

X

X

19

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

0

1,3

2

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Не вычеркнутые клетки результирующей таблицы соответствуют всем парам эквивалентных состояний.

Класс эквивалентности образуется состояниями, которые попарно эквивалентны. В данном случае образуются следующие пары эквивалентных состояний: q₅ и q₆, q₅ и q₇, q₆ и q₇, q₈ и q₉, q₁₁ и q₁₄, q₁₂ и q₁₅, q₁₃ и q₁₆, q₁₃ и q₁₈, q₁₆ и q₁₈.

Всего восемь пар попарно эквивалентных состояний. Эти состояния образуют пять классов эквивалентности - {q₅ , q₆ , q₇}, {q₈ , q₉}, {q₁₁ , q₁₄}, {q₁₂, q₁₅} и {q₁₃, q₁₆ , q₁₈}.

Каждое состояние, не вошедшее ни в один класс эквивалентности, эквивалентно лишь само себе и само образует этот класс. В рассматриваемом примере к нерасчлененным пяти классам необходимо добавить еще семь классов эквивалентности: q₀; q₁₃; q₂; q₄; q₁₀; q₁₇; q₁₉.

Состояние минимального автомата обозначим буквами r с индексами

r₀={q₀}; r₁={q_1,3}; r₂=(q₂}; r₃={q₄}; r₄={q₅, q₆, q₇}; r₅={q₈, q₉}; r₆={q₁₀}; r₇={q₁₁, q₁₄}; r₈={q₁₂, q₁₅}; r₉={ q₁₃, q_16, q₁₈}; r₁₀={q₁₇}; r₁₁={q₁₉}.

Таким образом, минимальный автомат содержит 12 состояний, не считая состояния r₁₂⁼{q₂₀} "Ошибка". Орграф этого автомата приводится на рис. 5 (без указания состояния «Ошибка»), а таблица переходов - в табл. 7.

X2

X5

Рис.5

В этой таблице, также как и в табл. 5, незаполненные клетки соответствуют состоянию «Ошибка».

Таблица 7

	Х0	X1	Х2	Х3	Х4	Х5	Х6	Х7
r0			r4	r1				r6
r1			r2					r3
r2		r4
r3					r4
r4	r12	r5
r5							r0	r12
r6					r7	r7	r10
r7							r8
r8	r9
r9						r11
r10							r9
r11