4.Переход от недетерминированного автомата к детерминированному
Получим из недетерминированного автомата детерминированный.
q |
х0 |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
q0 |
|
|
q1,3 |
q7 |
|
|
|
q10 |
q1,3 |
|
q2,4 |
|
|
|
|
|
|
q2,4 |
q5 |
|
|
|
|
|
|
q6 |
q5 |
|
|
|
|
|
q8 |
|
q19 |
q6 |
|
|
|
|
|
q9 |
|
q19 |
q7 |
|
|
|
|
|
q9 |
|
q19 |
q8 |
|
|
|
q0 |
|
|
|
q19 |
q9 |
|
|
|
q0 |
|
|
|
q19 |
q10 |
|
|
|
|
q11 |
q14 |
|
q17 |
q11 |
q12 |
|
|
|
|
|
|
|
q12 |
|
q13 |
|
|
|
|
|
|
q13 |
q19 |
|
|
|
|
|
|
|
q14 |
q15 |
|
|
|
|
|
|
|
q15 |
|
q16 |
|
|
|
|
|
|
q16 |
q19 |
|
|
|
|
|
|
|
q17 |
|
|
|
q18 |
|
|
|
|
q18 |
q19 |
|
|
|
|
|
|
|
q19 |
|
|
|
|
|
|
|
|
Граф переходов детерминированного автомата
х1
х0
х3
х5
х7
х7
х7
х7
х2
х5
х3
х7
х3
х7
х5
х0
х0
х1
х4
х1
х0
х0
х5
х3
х0
х7
5.Минимизация автомата методом прямоугольных таблиц.
Состояния разбиваем на классы эквивалентности; на базе этого разложения реализуем минимальный приведенный (все состояния достижимы) автомат.
q2,4 |
× |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
q5 |
× |
× |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
q6 |
× |
× |
q8,q9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
q7 |
× |
× |
q8,q9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
q8 |
× |
× |
× |
× |
× |
|
|
|
|
|
|
|
|
|
|
|
q9 |
× |
× |
× |
× |
× |
|
|
|
|
|
|
|
|
|
|
|
q10 |
× |
× |
× |
× |
× |
× |
× |
|
|
|
|
|
|
|
|
|
q11 |
× |
× |
× |
× |
× |
× |
× |
× |
|
|
|
|
|
|
|
|
q12 |
× |
× |
× |
× |
× |
× |
× |
× |
× |
|
|
|
|
|
|
|
q13 |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
|
|
|
|
|
|
q14 |
× |
× |
× |
× |
× |
× |
× |
× |
q12,q15 |
× |
× |
|
|
|
|
|
q15 |
× |
× |
× |
× |
× |
× |
× |
× |
× |
q13,q16 |
× |
× |
|
|
|
|
q16 |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
|
× |
× |
|
|
|
q17 |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
|
|
q18 |
× |
× |
× |
× |
× |
× |
× |
× |
× |
× |
|
× |
× |
|
× |
|
|
q1,3 q2,4 q5 q6 |
q7 |
q8 |
q9 |
q10 |
q11 |
q12 |
q13 |
q14 |
q15 |
q16 |
q17 |
|
|||
Вывод – из рассмотренных классов, эквивалентны:
5 ~ 6 ~ 7; 8 ~ 9; 11 ~ 14; 12 ~ 15; 13 ~ 16 ~ 18
Введем следующие обозначения:
r0 = q0; r1 = q1,3; r2 = q2,4; r3 = q5,6,7; r4 = q8,9; r5 = q10; r6 = q11,14; r7 = q12,15; r8 = q13,16,18; r9 = q17; r10 = q19; r11 = q20
q |
r |
х0 |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
q0 |
r0 |
|
|
r1 |
r3 |
|
|
|
r5 |
q1,3 |
r1 |
|
r2 |
|
|
|
|
|
|
q2,4 |
r2 |
r3 |
|
|
|
|
|
|
r3 |
q5,6,7 |
r3 |
|
|
|
|
|
r4 |
|
r10 |
q8,9 |
r4 |
|
|
|
r0 |
|
|
|
r10 |
q10 |
r5 |
|
|
|
|
r6 |
r6 |
|
r9 |
q11,14 |
r6 |
r7 |
|
|
|
|
|
|
|
q12,15 |
r7 |
|
r8 |
|
|
|
|
|
|
q13,16,18 |
r8 |
r10 |
|
|
|
|
|
|
|
q17 |
r9 |
|
|
|
r8 |
|
|
|
|
q19 |
r10 |
|
|
|
|
|
|
|
|
q20 |
r11 |
– |
– |
– |
– |
– |
– |
– |
– |
Окончательный граф этого автомата с условием введенного обозначения имеет вид:
