4. Сведение недетерминированного автомата к детерминированному

Недетерминированность автомата локально проявляется в том, что из екоторого его состояния q_i исходит несколько дуг, помеченных одним и тем же символом х_j, как показано на рис.2.

x_r

q_i

q_l

q_k

x_j

x_p

x_j

x_s

Рис. 2. Пример устранения недетерминированности

В этом случае недетерминированность устраняется склеиванием двух состояний q_l и q_k в одно – q_l,k . При этом q_l,k инцидентны все исходящие дуги x_s, x_p, x_r, являющиеся исходящими дугами вершин q_l и q_k .

x_s

В результате применения алгоритма нахождения детерминированного автомата, от автомата рис. 1 можно перейти к эквивалентному детерминированному автомату, таблица переходов которого приведена в табл. 5, а соответствующий ей граф переходов – на рис. 4.

Таблица 5.

q	x0	x1	x2	x3	x4	x5	x6	x7
q0	q1,3			q7				q10
q1,3		q2						q4
q2					q5
q4						q6
q5			q19			q8
q6			q19			q9
q7			q19			q9	q11,17	q14
q8	q0	q19
q9	q0	q19
q10	q14					q17	q11
q11				q12
q12				q13
q13				q19
q14				q15
q15				q16
q16				q19
q17				q18
q18				q19
q19

Рис. 4: Граф переходов детерминированного автомата, эквивалентного исходному.

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

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

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

Таблица 6.

q₁₂; q₁₅

q₁₂; q₁₃

1,3

X

q8 ,q9; q19 q8 ,q9; q19

q12; q16 q12; q18 q12; q19 q13; q15

2

X

X

4

X

X

X

5

X

X

X

X

q13; q19 q13; q16 q13; q18 q19; q15

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

q19; q16

10

X

X

X

X

X

X

X

X

X

q19; q18

11

X

X

X

X

X

X

X

X

X

X

q15; q16 q15; q18 q15; q19

12

X

X

X

X

X

X

Х

X

X

X

13

X

X

X

X

Х

Х

X

X

X

X

q16; q19

14

X

X

X

X

X

X

X

X

X

X

q16;q18

q19; q18 q18; q18

15

X

X

X

X

X

X

Х

X

X

X

16

X

X

X

X

Х

Х

X

X

X

X

17

X

X

X

X

Х

Х

X

X

X

X

18

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

2

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Не вычеркнутые клетки результирующей таблицы соответствуют всем парам эквивалентных состояний. Класс эквивалентности образуется состояниями, которые попарно эквивалентны. В данном случае получаем 6 пар, попарно эквивалентных состояний: q₅ и q₆, q₈ и q₉, q₁₂ и q₁₅, q₁₃ и q₁₆, q₁₃ и q₁₈, q₁₆ и q₁₈. Эти состояния образуют четыре классов эквивалентности {q₅, q₆}; {q₈, q₉};{q₁₂, q₁₅ };{q₁₃, q₁₆, q₁₈} . Каждое состояние, не вошедшие ни в один класс эквивалентности, эквивалентно лишь само себе и само образует этот класс. В моем примере к перечисленным пяти классам необходимо добавить еще шесть классов эквивалентности: q_1,3; q₂; q₄; q₁₀; q₁₉; q₀.

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

r₀ = {q₅, q_6, q₇}, r₁ = { q₈, q₉}, r₂ = {q₁₂, q_15, q₁₇}, r₃ = {q₁₃, q₁₆, q₁₈}, r₄ = {q_1,3}, r₅ = {q₂}, r₆ = {q₄}, r₇ = {q₁₀}, r₈ = {q₁₁}, r₉ = {q₁₄}, r₁₀ = {q₁₉}, r₁₁ = {q₀};

Граф переходов этого автомата приведен ни рис.5, а таблица переходов – в табл. 7.

Рис. 5 Граф переходов минимального распознающего автомата

Таблица 7.

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