Основы синтеза и диагностирования автоматов. Воронин В.В. - 191 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

Составители: 

Рубрика: 

187
ются одноэлементными, и поэтому все остальные со-
стояния автомата будут неэквивалентными. Алгоритм
останавливаем. Состояния (3,4) заменяем одним лю-
бым номером (например, номером 3) и окончательно
автоматная совмещённая таблица преобразуется к сле-
дующему виду (табл. 5.14). Далее состояния в табл.
5.14 перенумеруем последовательными номерами (0,
s
0
), (1, s
1
), (2, s
2
), (3, s
3
), (5, s
4
), (7, s
5
) и получим окончательную ав-
томатную таблицу (табл. 5.15), из которой видно, что получен ми-
нимальный автомат.
Из рассмотренного примера ясно как следует веси себя в общем
случае. Правда, остались без ответа два вопроса: 1)
почему совпадение подмножеств k-разбиения с ка-
ким-либо подмножеством k-1-разбиения свидетельст-
вует об эквивалентности состояний,
попавших в эти
подмножества; 2) почему процедура заканчивается за
конечное число шагов выделением всем имеющихся в
автомате эквивалентных состояний. В теории автома-
тов есть ответы на эти вопросы. Если минимизируется частичный
автомат, то неопределённые переходы и выходы следует доопреде-
лить таким образом, чтобы появилось больше строк, попавших в од-
но подмножество 1
-разбиения.
Иногда получить минимальную
форму автомата можно последова-
тельным объединением явно эквива-
лентных состояний в одно состояние.
Покажем этот процесс на примере
табл.5.10. В таблице пары (s
1
,s
5
) и
(s
2
,s
6
) являются явно эквивалентны-
Таблица 5.14
x
k
s
i
0 1
0
1
2
3
5
7
0/0
2/0
3/1
1/0
7/0
0/0
1/0
7/1
2/0
3/0
1/1
5/0
Таблица 5.15
x
k
s
i
0 1
s
0
s1
s
2
s
3
s
4
s
5
s
0
/0
s
2
/0
s
3
/1
s
1
/0
s
5
/0
s
0
/0
s
1
/0
s
5
/1
s
2
/0
s
3
/0
s
1
/1
s
4
/0
Таблица 5.16
x
k
x
k
s
i
x
1
x
2
x
3
x
1
x
2
x
3
s
1
s
2
s
3
s
4
s
7
s
8
s
2
s
2
s
2
s
8
s
2
s
8
s
1
s
2
s
2
s
3
s
2
s
7
s
1
s
1
s
7
s
1
s
3
s
1
1
0
0
1
0
1
0
1
1
0
1
0
1
1
1
1
1
1

Страницы