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

Построение минимального (но числу состояний) автомата, эквивалентного полученному в предыдущем разделе полностью определенному детеминированному конечному автомату, осуществляется в два этапа. На первом находится разбиение состояний автомата на классы эквивалентности, а на втором строится минимальный (иначе - приведенный) автомат. В начале составляется треугольная таблица (табл.6), клетки которой соответствуют всем парам (q_i, q_j), i≠j рабочих состояний. Она заполняется следующим образом. Если для рабочих состояний q_i и q_j в таблице существует входной символ х_k, при котором переход из q_i осуществляется в одно из рабочих состояний, а из q_j - в состояние ошибки, то состояния q_j и q_j не эквивалентны, и соответствующая им клетка помечается крестом. Иначе, если какие-либо две строчки табл.5 содержат разное число рабочих состояний или отличаются позициями, занимаемыми рабочими состояниями, то обозначающие это строки состояния не эквивалентны. В противном случае в клетку таблицы 6 с координатами q_i, q_j запишем каждую пару состояний (q_v, q_w), в которые автомат может перейти из q_i и q_j при подаче одного и того же входного символа.

Таблица 6

1,3,7

X

2

X

X

4

X

X

X

5

X

X

X

X

6

X

X

X

X

8

X

X

X

X

X

X

9

X

X

X

X

X

X

10

X

X

X

X

X

X

X

X

11

X

X

X

X

X

X

X

X

X

12

X

X

X

X

X

X

X

X

X

X

13

X

X

X

X

X

X

X

X

X

X

X

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

16

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

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

0

1,3,7

2

4

5

6

8

9

10

11

12

13

14

15

16

17

18

В итоге невычеркнутые клетки табл. 6 соответствуют всем парам

эквивалентных состояний. Класс эквивалентности образуется состояниями,

которые попарно эквивалентны. В данном случае получается 4 класса

эквивалентности: {q₅, q₆}, {q₈, q₉,}, {q₁₂, q₁₅},{q₁₃, q₁₆, q₁₈}. Каждое

состояние, не вошедшее ни в один класс эквивалентности, эквивалентно

лишь само себе и само образует этот класс. В нашем примере к

перечисленным классам необходимо добавить еще 9 классов

эквивалентности: q₀, q_1,3,7, q₂, q₄, q₁₀, q₁₁, q₁₄, q₁₇, q₁₉,

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

r₀={q₅, q₆}, r₁={q₈, q₉}, r₂={q₁₂, q₁₅}, r₃={q₁₃, q₁₆, q₁₈}, r₄={q_1,3,7},

r₅={q₂}, r₆={q₄}, r₇={q₁₀}, r₈={q₁₁}, r₉={q₁₄}, r₁₀={q₁₇}, r₁₁={q₁₉}, r₁₂={q₀}.

Минимальный автомат содержит, таким образом, 13 состояний, не считая состояния ОШИБКА. Граф переходов этого автомата приведен на рис. 3, а таблица переходов - в табл. 7

Рисунок 3

Таблица 7

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