Материал: Ковригин Теория автоматов Лабораторный практикум 2012
11. Находим первую пару ближайших скобок на позициях 4 и 8; заменяем пару CF на ·-node (K); C и F – левое и правое поддеревья для K:
РВ |
( |
1 |
0 |
1 |
( |
K |
J |
) |
+ |
1 |
0 |
1 |
) |
№ поз. |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
12. |
Заменяем пару KJ на ·-node (L); K и J – левое и правое под- |
||||||||||||||||
деревья для L: |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
РВ |
( |
1 |
0 |
1 |
( |
L |
) |
+ |
1 |
0 |
1 |
) |
|
||
|
|
№ поз. |
0 |
1 |
2 |
3 |
4 |
5 |
|
6 |
7 |
8 |
9 |
10 |
11 |
|
|
13. |
Заменяем триаду (L) на L: |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
РВ |
( |
1 |
0 |
1 |
L |
+ |
1 |
0 |
1 |
) |
|
|
||
|
|
|
№ поз. |
0 |
1 |
2 |
3 |
4 |
|
5 |
6 |
7 |
8 |
9 |
|
|
|
14. |
Находим очередную пару ближайших скобок в позициях 0 |
||||||||||||||||
и 9; заменяем позиции 2 и 7 на 0-node (M, N), позиции 1, 3, 6 и 8 на
1-node (P, Q, R, S)
|
|
|
РВ |
( |
P |
M |
Q |
L |
+ |
R |
N |
S |
) |
|
||||||||||||||||||
|
|
№ поз. |
0 |
|
1 |
|
2 |
|
3 |
|
4 |
5 |
6 |
|
|
7 |
|
8 |
9 |
|
||||||||||||
15. |
Заменяем пару L+ на +-node (T); L – поддерево для T: |
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
РВ |
|
( |
|
P |
M |
Q |
T |
R |
|
N |
|
S |
|
) |
|
|
||||||||||||
|
|
|
№ поз. |
|
0 |
|
1 |
2 |
3 |
4 |
5 |
|
6 |
|
7 |
|
8 |
|
|
|||||||||||||
16. |
Заменяем пару PM на ·-node (U); |
P и M – левое и правое |
||||||||||||||||||||||||||||||
поддеревья для U: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
РВ |
|
( |
|
U |
|
Q |
|
T |
R |
N |
|
|
S |
|
) |
|
|
|
||||||||||
|
|
|
|
№ поз. |
0 |
|
1 |
|
2 |
|
3 |
4 |
5 |
|
|
6 |
|
7 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
91
17. |
Заменяем пару UQ на ·-node (V); |
U и Q – левое и правое |
|||||||||||||||||||||||
поддеревья для V: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
РВ |
( |
|
V |
T |
R |
N |
|
S |
|
) |
|
|||||||||||
|
|
№ поз. |
0 |
|
1 |
2 |
3 |
4 |
|
5 |
|
6 |
|
||||||||||||
18. |
Заменяем пару VT на ·-node (W); V и T – левое и правое под- |
||||||||||||||||||||||||
деревья для W: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
РВ |
|
( |
|
|
W |
R |
|
N |
|
S |
|
|
) |
|
|
||||||
|
|
|
№ поз. |
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
|
5 |
|
|
||||||||
19. |
Заменяем пару WR на ·-node (X); |
W и R – левое и правое |
|||||||||||||||||||||||
поддеревья для X: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
РВ |
( |
X |
N |
S |
|
) |
|
|
|
|
||||||||||
|
|
|
|
№ поз. |
0 |
1 |
2 |
3 |
|
4 |
|
|
|
|
|||||||||||
20. |
Заменяем пару XN на ·-node (Y); X и N – левое и правое под- |
||||||||||||||||||||||||
деревья для Y: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
РВ |
|
( |
|
Y |
S |
|
) |
|
|
|
|
|
|
|||||
|
|
|
|
|
№ поз |
0 |
|
1 |
|
2 |
|
3 |
|
|
|
|
|
|
|||||||
21. |
Заменяем пару YS на ·-node (Z); Y и S – левое и правое под- |
||||||||||||||||||||||||
деревья для Z: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
РВ |
( |
Z |
) |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
№ поз |
0 |
1 |
2 |
|
|
|
|
|
|
|
||||||||
22. |
Заменяем триаду (Z) на Z: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
РВ |
|
|
|
Z |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
№ поз. |
0 |
|
|
|
|
|
|
|
|
|
|||||||
23. |
Корнем дерева является Z. |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
92 |
|
|
|
|
|
|
|
|
|
|
|
||||
Построенное дерево приведено на рис. 6.9. |
|
|
||||
|
|
|
|
Z(·) |
|
|
|
|
|
|
Y(·) |
S(1) |
|
|
|
|
X(·) |
N(0) |
|
|
|
|
|
W(·) |
R(1) |
|
|
|
V(·) |
|
|
T(+) |
|
|
|
U(·) |
Q(1) |
|
L(·) |
|
|
P(1) |
M(0) |
|
K(·) |
|
|
J(|) |
|
C(|) |
|
|
F(|) |
G(0) |
H(1) |
|
A(0) |
B(1) |
D(0) |
E(1) |
|
|
Рис. 6.9. Синтаксическое дерево для регулярного выражения
101((0|1)(0|1)(0|1))+101
93
Синтез недетерминированного конечного автомата
Для синтеза недетерминированного автомата воспользуемся рекурсивным обходом дерева в порядке левое поддерево – правое поддерево – корень (post-order), и синтезируем автоматы для посещаемых узлов в соответствии с модифицированным алгоритмом МакНортона–Ямады–Томпосона.
1.От корня спускаемся до узла P, синтезируем автомат N1 по правилу 2.
2.Возвращаемся в узел U, посещаем узел M, синтезируем автомат N2 по правилу 2.
3.Возвращаемся в узел U, синтезируем автомат N3 по правилу 4, объединяя автоматы N1 и N2.
4.Возвращаемся в узел V, посещаем узел Q, синтезируем автомат N4 по правилу 2.
5.Возвращаемся в узел V, синтезируем автомат N5 по правилу 4, объединяя автоматы N3 и N4.
6.Возвращаемся в узел W, спускаемся до узла A, синтезируем автомат N6 по правилу 2.
7.Возвращаемся в узел C, посещаем узел B, синтезируем автомат N7 по правилу 2.
8.Возвращаемся в узел C, синтезируем автомат N8 по правилу 3, объединяя автоматы N6 и N7.
9.Возвращаемся в узел K, спускаемся в узел D, синтезируем автомат N9 по правилу 2.
10.Возвращаемся в узел F, посещаем узел E, синтезируем автомат N10 по правилу 2.
11.Возвращаемся в узел F, синтезируем автомат N11 по правилу 3, объединяя автоматы N9 и N10.
12.Возвращаемся в узел K, синтезируем автомат N12 по правилу 4, объединяя автоматы N7 и N11.
13.Возвращаемся в узел L, спускаемся в узел G, синтезируем автомат N13 по правилу 2.
14.Возвращаемся в узел J, посещаем узел H, синтезируем автомат N14 по правилу 2.
15.Возвращаемся в узел J, синтезируем автомат N15 по правилу 3, объединяя автоматы N13 и N14.
94
16.Возвращаемся в узел L, синтезируем автомат N16 по правилу 4, объединяя автоматы N12 и N15.
17.Возвращаемся в узел T, синтезируем автомат N17 по правилу 6, преобразуя автомат N17.
18.Возвращаемся в узел W, синтезируем автомат N18 по правилу 4, объединяя автоматы N5 и N17.
19.Возвращаемся в узел X, посещаем узел R, синтезируем автомат N19 по правилу 2.
20.Возвращаемся в узел X, синтезируем автомат N20 по правилу 4, объединяя автоматы N18 и N19.
21.Возвращаемся в узел Y, посещаем узел N, синтезируем автомат N21 по правилу 2.
22.Возвращаемся в узел Y, синтезируем автомат N22 по правилу 4, объединяя автоматы N20 и N21.
23.Возвращаемся в узел Z, посещаем узел S, синтезируем автомат N23 по правилу 2.
24.Возвращаемся в узел Z, синтезируем автомат N24 по правилу 4, объединяя автоматы N22 и N23.
25.Так как мы вернулись и обработали корень дерева, то синтез автомата завершен.
Граф переходов автомата приведен на рис. 6.10, таблица переходов приведена в табл. 6.1. Состояние S0 является стартовым, принимающим является состояние S23.
Очевидно, что данный недетерминированный конечный автомат не является единственным, так как благодаря наличию ε-переходов можно построить бесконечное множество автоматов, соответствующих данному регулярному выражению. Данный автомат также не является и минимальным, так как количество состояний в автомате, представленном на рис. 6.10, может быть сокращено. Но в данном сокращении нет необходимости, так как данный автомат в дальнейшем будет преобразован в детерминированный конечный автомат. При этом алгоритм построения недетерминированного конечного автомата, которым мы воспользовались, гарантирует верхнюю границу анализируемых состояний автомата и количество переходов из его состояний, что делает дальнейшие этапы синтеза более предсказуемыми с точки зрения вычислительной сложности.
95