Материал: Ковригин Теория автоматов Лабораторный практикум 2012
6.Из табл. П3.6 видно, что группу G8 необходимо разбить на подгруппы. Результирующее разбиение после третьей итерации приведено в табл. П4.7.
7.Построим очередное соответствие переходов для текущего разбиения на группы. Результат построения приведен в табл. П4.8.
Таблица П4.8 Итерация 4. Соответствия переходов для разбиения на группы состояний
автомата, соответствующего регулярному выражению 101((0|1)(0|1)(0|1))+101
Группа |
Сигнал |
Состояния |
Переход |
G1 |
0 |
M |
G9 |
|
1 |
M |
G6 |
G2 |
0 |
Ø |
G2 |
|
1 |
Ø |
G2 |
G3 |
0 |
A |
G2 |
|
1 |
A |
G4 |
G4 |
0 |
B |
G7 |
|
1 |
B |
G2 |
G5 |
0 |
L |
G8 |
|
1 |
L |
G1 |
G6 |
0 |
K |
G5 |
|
1 |
K |
G9 |
G7 |
0 |
C |
G2 |
|
1 |
C |
G9 |
G8 |
0 |
I, J |
G9 |
|
1 |
I, J |
G6 |
G9 |
0 |
G, H |
G8 |
|
|
D, E, F |
G9 |
|
1 |
G, H |
G8 |
|
|
D, E, F |
G9 |
8. Из табл. П4.8 видно, что группу G9 необходимо разбить на несколько подгрупп. При этом разбиения для всех входных сигналов совпадают, поэтому можно не строить объедение пересечений подгрупп разбиений, а сформировать новое разбиение сразу. Результирующее разбиение после четвертой итерации приведено в табл. П4.9.
186
Таблица П4.9 Разбиение на группы состояний автомата, соответствующего регулярному
выражению 101((0|1)(0|1)(0|1))+101, после четвертой итерации
Группа |
Состояния |
Комбинация сигналов |
G1 |
M |
GOOD = ‘1’, BAD = ‘0’ |
G2 |
Ø |
GOOD = ‘0’, BAD = ‘1’ |
G3 |
A |
GOOD = ‘0’, BAD = ‘0’ |
G4 |
B |
GOOD = ‘0’, BAD = ‘0’ |
G5 |
L |
GOOD = ‘0’, BAD = ‘0’ |
G6 |
K |
GOOD = ‘0’, BAD = ‘0’ |
G7 |
C |
GOOD = ‘0’, BAD = ‘0’ |
G8 |
I, J |
GOOD = ‘0’, BAD = ‘0’ |
G9 |
G, H |
GOOD = ‘0’, BAD = ‘0’ |
G10 |
D, E, F |
GOOD = ‘0’, BAD = ‘0’ |
9. Продолжим построение соответствий переходов для текущего разбиения на группы. Результат построения на данной итерации приведен в табл. П4.11.
10.Очевидно, что на данном шаге группу G10 необходимо разбить на несколько подгрупп. Результирующее разбиение после четвертой итерации приведено в табл. П4.10.
Таблица П4.10 Разбиение на группы состояний автомата, соответствующего регулярному
выражению 101((0|1)(0|1)(0|1))+101, после пятой итерации
Группа |
Состояния |
Комбинация сигналов |
G1 |
M |
GOOD = ‘1’, BAD = ‘0’ |
G2 |
Ø |
GOOD = ‘0’, BAD = ‘1’ |
G3 |
A |
GOOD = ‘0’, BAD = ‘0’ |
G4 |
B |
GOOD = ‘0’, BAD = ‘0’ |
G5 |
L |
GOOD = ‘0’, BAD = ‘0’ |
G6 |
K |
GOOD = ‘0’, BAD = ‘0’ |
G7 |
C |
GOOD = ‘0’, BAD = ‘0’ |
G8 |
I, J |
GOOD = ‘0’, BAD = ‘0’ |
G9 |
G, H |
GOOD = ‘0’, BAD = ‘0’ |
G10 |
E, F |
GOOD = ‘0’, BAD = ‘0’ |
G11 |
D |
GOOD = ‘0’, BAD = ‘0’ |
187
Таблица П4.11 Итерация 5. Соответствия переходов для разбиения на группы состояний
автомата, соответствующего регулярному выражению 101((0|1)(0|1)(0|1))+101
Группа |
Сигнал |
Состояния |
Переход |
G1 |
0 |
M |
G10 |
|
1 |
M |
G6 |
G2 |
0 |
Ø |
G2 |
|
1 |
Ø |
G2 |
G3 |
0 |
A |
G2 |
|
1 |
A |
G4 |
G4 |
0 |
B |
G7 |
|
1 |
B |
G2 |
G5 |
0 |
L |
G8 |
|
1 |
L |
G1 |
G6 |
0 |
K |
G5 |
|
1 |
K |
G9 |
G7 |
0 |
C |
G2 |
|
1 |
C |
G10 |
G8 |
0 |
I, J |
G10 |
|
1 |
I, J |
G6 |
G9 |
0 |
G, H |
G8 |
|
1 |
G, H |
G8 |
G10 |
0 |
E, F |
G9 |
|
|
D |
G10 |
|
1 |
E, F |
G9 |
|
|
D |
G10 |
11.Построим соответствие переходов для разбиения на группы после пятой итерации. Результат построения на данной итерации приведен в табл. П4.12. Отметим, что на данном этапе мы не получили несоответствия переходов ни для одной группу из текущего разбиения. Следовательно, на прошлой итерации было получено окончательное разбиение, соответствующее минимальному количеству состояний в детерминированном конечном автомате.
12.Получено минимальное разбиение автомата на группы состояний. Алгоритм шага 2 завершен.
188
Таблица П4.12 Итерация 6. Соответствия переходов для разбиения на группы состояний
автомата, соответствующего регулярному выражению 101((0|1)(0|1)(0|1))+101
Группа |
Сигнал |
Состояния |
Переход |
G1 |
0 |
M |
G10 |
|
1 |
M |
G6 |
G2 |
0 |
Ø |
G2 |
|
1 |
Ø |
G2 |
G3 |
0 |
A |
G2 |
|
1 |
A |
G4 |
G4 |
0 |
B |
G7 |
|
1 |
B |
G2 |
G5 |
0 |
L |
G8 |
|
1 |
L |
G1 |
G6 |
0 |
K |
G5 |
|
1 |
K |
G9 |
G7 |
0 |
C |
G2 |
|
1 |
C |
G11 |
G8 |
0 |
I, J |
G10 |
|
1 |
I, J |
G6 |
G9 |
0 |
G, H |
G8 |
|
1 |
G, H |
G8 |
G10 |
0 |
E, F |
G9 |
|
1 |
E, F |
G9 |
G11 |
0 |
D |
G10 |
|
1 |
D |
G10 |
Синтез минимального автомата. Шаг 3
Назначим представителей группам в соответствии с табл. П4.13. При этом принимающим состоянием (формирующим сигнал GOOD = ‘1’) будет представитель S10, а тупиковым (формирующим сигнал BAD = ‘1’) – представитель S2. Стартовым состоянием минимального автомата будет S0 – представитель, содержащий стартовое состояние исходного автомата. Граф переходов автомата приведен на рис. П4.1.
189
start
S0 |
1 |
S1 |
0 |
|
S3 |
|
|
|
|
|
1 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
0 |
S2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
S9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
0 |
|
|
0 |
0 |
|
1 |
|
|
|
|
|
0 |
|
||
|
S4 |
|
|
|
S5 |
S6 |
S7 |
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
1 |
1 |
S8 |
1 |
|
|
|
|
S10 |
||||
|
|
|
|
|
||||
|
|
|
|
|
|
|
1 |
|
Рис. П4.1. Граф переходов минимального детерминированного конечного автомата, соответствующего регулярному выражению 101((0|1)(0|1)(0|1))+101