Материал: Ковригин Теория автоматов Лабораторный практикум 2012
Таблица 6.9
Синтез таблицы переходов ДКА (шаг 8)
|
ДКА |
НКА |
0 |
1 |
|
|
A (*) |
S0 |
Ø |
B |
|
|
B (*) |
S1 |
C |
Ø |
|
|
C (*) |
S2 |
Ø |
D |
|
|
D (*) |
S3, S4, S5, S7 |
E |
F |
|
|
E (*) |
S6, S9, S10, S12 |
G |
H |
|
|
F (*) |
S8, S9, S10, S12 |
G |
H |
|
|
G (*) |
S11, S14, S15, S17 |
I |
J |
|
|
H |
S13, S14, S15, S17 |
|
|
|
|
I |
S4, S5, S7, S16, S19, S20 |
|
|
|
|
J |
S4, S5, S7, S18, S19, S20 |
|
|
|
|
|
|
|
Таблица 6.10 |
|
|
|
Синтез таблицы переходов ДКА (шаг 9) |
|
|
|
|
|
|
|
|
|
|
ДКА |
НКА |
0 |
1 |
|
|
A (*) |
S0 |
Ø |
B |
|
|
B (*) |
S1 |
C |
Ø |
|
|
C (*) |
S2 |
Ø |
D |
|
|
D (*) |
S3, S4, S5, S7 |
E |
F |
|
|
E (*) |
S6, S9, S10, S12 |
G |
H |
|
|
F (*) |
S8, S9, S10, S12 |
G |
H |
|
|
G (*) |
S11, S14, S15, S17 |
I |
J |
|
|
H (*) |
S13, S14, S15, S17 |
I |
J |
|
|
I |
S4, S5, S7, S16, S19, S20 |
|
|
|
|
J |
S4, S5, S7, S18, S19, S20 |
|
|
|
11. Строим множество zε(M0(J)) = {S6, S9, S10, S12}. Состояние, соответствующее такому множеству, уже есть в ДКА (E). Строим множество zε(M1(J)) = {S8, S9, S10, S12, S21}. Состояние, соответствующее такому множеству, также есть в ДКА (K). Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.12).
101
|
|
|
Таблица 6.11 |
||
|
Синтез таблицы переходов ДКА (шаг 10) |
|
|
|
|
|
|
|
|
|
|
ДКА |
НКА |
0 |
1 |
|
|
A (*) |
S0 |
Ø |
B |
|
|
B (*) |
S1 |
C |
Ø |
|
|
C (*) |
S2 |
Ø |
D |
|
|
D (*) |
S3, S4, S5, S7 |
E |
F |
|
|
E (*) |
S6, S9, S10, S12 |
G |
H |
|
|
F (*) |
S8, S9, S10, S12 |
G |
H |
|
|
G (*) |
S11, S14, S15, S17 |
I |
J |
|
|
H (*) |
S13, S14, S15, S17 |
I |
J |
|
|
I (*) |
S4, S5, S7, S16, S19, S20 |
E |
K |
|
|
J |
S4, S5, S7, S18, S19, S20 |
|
|
|
|
K |
S8, S9, S10, S12, S21 |
|
|
|
|
|
|
|
Таблица 6.12 |
||
|
Синтез таблицы переходов ДКА (шаг 11) |
|
|
|
|
|
|
|
|
|
|
ДКА |
НКА |
0 |
1 |
|
|
A (*) |
S0 |
Ø |
B |
|
|
B (*) |
S1 |
C |
Ø |
|
|
C (*) |
S2 |
Ø |
D |
|
|
D (*) |
S3, S4, S5, S7 |
E |
F |
|
|
E (*) |
S6, S9, S10, S12 |
G |
H |
|
|
F (*) |
S8, S9, S10, S12 |
G |
H |
|
|
G (*) |
S11, S14, S15, S17 |
I |
J |
|
|
H (*) |
S13, S14, S15, S17 |
I |
J |
|
|
I (*) |
S4, S5, S7, S16, S19, S20 |
E |
K |
|
|
J |
S4, S5, S7, S18, S19, S20 |
E |
K |
|
|
K |
S8, S9, S10, S12, S21 |
|
|
|
|
12. Строим множество zε(M0(K)) = {S11, S14, S15, S17, S22},
ставим ему в соответствие состояние ДКА L. Строим множество zε(M1(K)) = {S13, S14, S15, S17}. Состояние, соответствующее такому множеству, уже есть в ДКА (H). Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.13).
102
|
|
|
Таблица 6.13 |
|
|
Синтез таблицы переходов ДКА (шаг 12) |
|
|
|
|
|
|
|
|
ДКА |
НКА |
0 |
1 |
|
A (*) |
S0 |
Ø |
B |
|
B (*) |
S1 |
C |
Ø |
|
C (*) |
S2 |
Ø |
D |
|
D (*) |
S3, S4, S5, S7 |
E |
F |
|
E (*) |
S6, S9, S10, S12 |
G |
H |
|
F (*) |
S8, S9, S10, S12 |
G |
H |
|
G (*) |
S11, S14, S15, S17 |
I |
J |
|
H (*) |
S13, S14, S15, S17 |
I |
J |
|
I (*) |
S4, S5, S7, S16, S19, S20 |
E |
K |
|
J (*) |
S4, S5, S7, S18, S19, S20 |
E |
K |
|
K (*) |
S8, S9, S10, S12, S21 |
L |
H |
|
L |
S11, S14, S15, S17, S22 |
|
|
|
13. Строим множество zε(M0(L)) = {S4, S5, S7, S16, S19, S20}.
Состояние, соответствующее такому множеству, уже есть в ДКА (I). Строим множество zε(M1(L)) = {S4, S5, S7, S18, S19, S20, S23}, ставим ему в соответствие состояние ДКА M. Данное состояние будет принимающим для ДКА, так как содержит принимающее состояние НКА. Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.14).
14.Строим множество zε(M0(M)) = {S6, S9, S10, S12}. Состояние, соответствующее такому множеству, уже есть в ДКА (E).
Строим множество zε(M1(M)) = {S8, S9, S10, S12, S21}. Состояние, соответствующее такому множеству, также есть в ДКА (K). Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние.
15.В таблице переходов не осталось не помеченных состояний
–синтез детерминированного конечного автомата завершен
(табл. 6.15).
103
|
|
|
|
|
Таблица 6.14 |
|
|
|
Синтез таблицы переходов ДКА (шаг 13) |
|
|
||
|
|
|
|
|
|
|
|
ДКА |
НКА |
0 |
1 |
|
|
|
A (*) |
S0 |
Ø |
B |
|
|
|
B (*) |
S1 |
|
C |
Ø |
|
|
C (*) |
S2 |
Ø |
D |
|
|
|
D (*) |
S3, S4, S5, S7 |
|
E |
F |
|
|
E (*) |
S6, S9, S10, S12 |
|
G |
H |
|
|
F (*) |
S8, S9, S10, S12 |
|
G |
H |
|
|
G (*) |
S11, S14, S15, S17 |
|
I |
J |
|
|
H (*) |
S13, S14, S15, S17 |
|
I |
J |
|
|
I (*) |
S4, S5, S7, S16, S19, S20 |
|
E |
K |
|
|
J (*) |
S4, S5, S7, S18, S19, S20 |
|
E |
K |
|
|
K (*) |
S8, S9, S10, S12, S21 |
|
L |
H |
|
|
L (*) |
S11, S14, S15, S17, S22 |
|
I |
M |
|
|
M |
S4, S5, S7, S18, S19, S20, S23 |
|
|
|
|
|
|
|
|
|
Таблица 6.15 |
|
|
|
Синтез таблицы переходов ДКА (шаг 14) |
|
|
||
|
|
|
|
|
|
|
|
ДКА |
НКА |
|
0 |
1 |
|
|
A (*) |
S0 |
|
Ø |
B |
|
|
B (*) |
S1 |
|
C |
Ø |
|
|
C (*) |
S2 |
|
Ø |
D |
|
|
D (*) |
S3, S4, S5, S7 |
|
E |
F |
|
|
E (*) |
S6, S9, S10, S12 |
|
G |
H |
|
|
F (*) |
S8, S9, S10, S12 |
|
G |
H |
|
|
G (*) |
S11, S14, S15, S17 |
|
I |
J |
|
|
H (*) |
S13, S14, S15, S17 |
|
I |
J |
|
|
I (*) |
S4, S5, S7, S16, S19, S20 |
|
E |
K |
|
|
J (*) |
S4, S5, S7, S18, S19, S20 |
|
E |
K |
|
|
K (*) |
S8, S9, S10, S12, S21 |
|
L |
H |
|
|
L (*) |
S11, S14, S15, S17, S22 |
|
I |
M |
|
|
M (*) |
S4, S5, S7, S18, S19, S20, S23 |
|
E |
K |
|
Граф переходов синтезированного детерминированного конечного автомата приведен на рис. 6.11.
104
start
A |
1 |
B |
0 |
C |
|
|
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
0 |
Ø |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
0 |
|
0 |
|
|
|
|
|
|
|
E |
G |
I |
|
|
L |
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
D |
|
1 |
|
|
|
|
0 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
|
|
|
0 |
|
0 |
1 |
|
1 |
|
|
|
|
F |
H |
J |
K |
||
|
|
|
|
|
M |
||||
|
|
|
|
|
|
1 |
|
|
|
1 |
0 |
|
|
|
1 |
Рис. 6.11. Граф переходов детерминированного конечного автомата, соответствующего регулярному выражению 101((0|1)(0|1)(0|1))+101