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

UptoLike

ВУЗ: 

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

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

Рубрика: 

183
В случаях 3 и 4 состояния s
i
и s
j
называют явно эквивалентны-
ми, а автомат, имеющий такие состояния – явно сократимым. Будем
иллюстрировать понятие эквивалентности состояний следующей ав-
томатной таблицей (табл. 5.10).
Из таблицы видно, что строки s
1
и s
5
одинаковы, а строки s
2
и s
6
ста-
новятся одинаковыми, если каждый
символ s
2
заменить на s
6
(или наобо-
рот). Следовательно, пары состояний
(s
1
,s
5
) и (s
2
,s
6
) явно эквивалентны, а
автомат является явно сократимым.
Также можно заключить, что состоя-
ния множеств {s
1
,s
4
,s
5
,s
8
} и {s
2
,s
3
,s
6
,s
7
}
не могут быть эквивалентными и являются явно различимыми.
Кроме явно эквивалентных состояний в автомате могут сущест-
вовать и другие эквивалентные состояния, выявить
которые при визуальном анализе автоматной таб-
лицы трудно. Поэтому разработаны различные ре-
гулярные методы поиска таких скрытых состояний.
Все они базируются на понятии k-эквивалентности.
Состояния s
i
и s
j
k-эквивалентны, если любое входное слово
длинной k символов P
q
вызывает в двух экземплярах автомата, нахо-
дящихся в этих состояниях, одинаковую реакцию или Q
qi
=Q
qj
(рис.
5.20). Здесь P
q
=x
q1
x
q2
…x
qk
и Q
qi
=y
q1
y
q2
…y
qk
. Другими словами, при
входной последовательности длины k нельзя отличить по выходной
последовательности в каком из состояний, s
i
или s
j
, находится авто-
мат. В противном случае состояния называют k-различимыми. Если
множество состояний автомата S разбить на систему не пересекаю-
щихся подмножеств P
k
={S
1
,S
2
, …}, S
i
∩
S
j
=
∅
, S
i
∈
S по следующим
Таблица 5.10
s(t+1)
y(t)
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
5
s
6
s
7
s
8
s
2
s
6
s
2
s
8
s
2
s
2
s
6
s
8
s
5
s
2
s
2
s
3
s
5
s
6
s
6
s
7
s
5
s
5
s
7
s
1
s
5
s
5
s
3
s
5
1
0
0
1
1
0
0
1
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1
s
j
Q
qi
Q
qj
P
q
Рис. 5.20
s
i

Страницы