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