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

UptoLike

ВУЗ: 

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

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

Рубрика: 

182
исходный автомат. Методики нахождения минимальной формы бази-
руются на понятии эквивалентных состояний.
Состояния s
i
и s
j
эквивалентны, если любое входное слово P
k
вызывает в двух экземплярах автомата, находящихся в этих состоя-
ниях, одинаковую реакцию или Q
ki
=Q
kj
(рис. 5.19). Здесь P
k
=x
k1
x
k2
x
k3
… и Q
ki
=y
k1
y
k2
y
k3
…. В этом случае записывают s
i
=s
j
; в противном
случае - s
i
≠
s
j
. Из определения эквивалентности состояний следует,
что данное свойство рефлексивно (s
i
=s
i
), симмет-
рично (если s
i
=s
j
, то s
j
=s
i
) и транзитивно (если s
i
=s
j
и s
j
=s
k
, то s
i
=s
k
), т.е. это обычное отношение экви-
валентности, которое применимо к множеству со-
стояний любой мощности. Различимость состояний
не обладает свойством рефлексивности и транзитивности, поэтому
оно может относиться только к парам состояний.
При анализе эквивалентности состояний пользуются чаще всего
автоматной таблицей, но её модернизируют к такому виду, какой
имеет табл. 5.9.
Для
таких таблиц спра-
ведливо следующее.
1. Если строки s
i
и s
j
в
подтаблице для y(t) различа-
ются, то s
i
≠
s
j
, и эти состоя-
ния явно различимы.
2. Если первое утвер-
ждение справедливо для всех пар состояний, т.е.
∀
(i,j)
∈
{0,1, … ,q} и
i
≠
j, то автомат будет явно минимальным.
3. Если строки s
i
и s
j
в полной таблице совпадают, то s
i
=s
j
.
4. Если строки s
i
и s
j
полной таблицы становятся одинаковыми
при замене каждого обозначения s
i
на s
j
(или наоборот), то s
i
=s
j
.
Таблица 5.9
s(t+1)
y(t)
x
k
x
k
s
i
x
1
x
2
… x
n
x
1
x
2
…
x
n
s
0
s
1
.
.
.
s
q
s
j
Q
ki
Q
kj
P
k
Рис. 5.19
s
i

Страницы