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

UptoLike

ВУЗ: 

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

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

Рубрика: 

185
(табл. 5.11) задан своей автоматной таблицей. Для задачи минимиза-
ции удобнее поменять строки и столбцы автоматной таблицы.
Первый этап минимизации состоит в выделении подмножеств
состояний, которые могут быть совмещены по своим выходным сиг-
налам при подаче на вход автомата вход-
ной последовательности длины 1. Это
можно сделать, если автомат не является
явно минимальным, т.е. существуют со-
стояния s
i
и s
j
, для которых
λ
(x
k
,s
i
)=
λ
(x
k
,s
j
), k=1,n.
Результат выделения таких подмно-
жеств называют 1-разбиением, и их можно
получить, просматривая таблицу выходов
и объединяя в одно подмножество те состояния, для которых соот-
ветствующие им строки совпадают. Для нашего примера имеем
α
1
={0,3,4,7};
β
1
={1,5,6};
γ
1
={2}.
Если автомат является явно минимальным, то 1-разбиение даёт
q одноэлементных подмножеств. В каждом подмножестве 1-
разбиения ищем эквивалентные состояния. С этой целью производим
попарное сравнение строк таблицы переходов и находим одинаковые
строки, состояния которых относятся к одному подмножеству. Для
класса
α
1
сравниваемыми парами будут следующие:
(0,3); (0,4); (0,7); (3,4); (3,7); (4,7),
все они не образуют эквивалентные пары состояний. Для
β
1
имеем
(1,5); (1,6); (5,6),
где пара (1,6) является парой эквивалентных состояний. Найденную
пару можно заменить одним состоянием, присвоив ему, например,
номер 1 (состояние 6 – лишнее). Эквивалентные состояния в 1-
разбиении существуют только тогда, когда автомат является явно
Таблица 5.11
δ
(x
k
,s
i
)
λ
(x
k
,s
i
)
x
k
x
k
s
i
0 1
s
i
0 1
0
1
2
3
4
5
6
7
0
2
3
1
6
7
2
0
1
7
2
4
3
6
7
5
0
1
2
3
4
5
6
7
0
0
1
0
0
0
0
0
0
1
0
0
0
1
1
0

Страницы