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