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

UptoLike

ВУЗ: 

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

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

Рубрика: 

188
ми. Обозначим их, соответственно, s
1
и s
2
, а строки s
5
и s
6
вычерк-
нем и заменим в таблице s
5
на s
1
и s
6
на s
2
. Получим автомат, экви-
валентный исходному и имеющий автоматную таблицу в виде табл.
5.16. В этой таблице пара (s
3
,s
7
) является явно эквивалентной. Вы-
черкнем строку s
7
и заменим s
7
на s
3
, получим табл. 5.17.
В данной таблице состояния s
4
и
s
8
также явно эквивалентны. Продела-
ем вышеприведённую процедуру с
этими состояниями и получим экви-
валентный автомат, в котором уже
нет явно эквивалентных состояний
(табл. 5.18). Можно показать, что он минимальный. Для полученного
автомата граф переходов представлен на рис. 5.21. По графу видно,
что подавтомат (s
1
,s
2
) – тупиковый, а
состояние s
4
– приходящее.
Исходя из содержательного опи-
сания проектируемого устройства, его
формальное описание в виде абст-
рактного автомата можно получить и
в минимальной форме, и в избыточной. Всё зависит от опыта разра-
ботчика.
Приведём пример. Опишем
следующую игру в виде абстракт-
ного автомата. Монета подбрасы-
вается многократно; очко засчиты-
вается при k-
м подбрасывании, ес-
ли при (k-2)-м , (k-1)-м и k-м под-
брасывании выпадают, соответст-
венно, ЦГГ или ГГГ (Ц – цифра, Г -
Таблица 5.17
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
8
s
2
s
2
s
2
s
8
s
8
s
1
s
2
s
2
s
3
s
3
s
1
s
1
s
3
s
1
s
1
1
0
0
1
1
0
1
1
0
0
1
1
1
1
1
Таблица 5.18
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
2
s
2
s
2
s
4
s
1
s
2
s
2
s
3
s
1
s
1
s
3
s
1
1
0
0
1
0
1
1
0
1
1
1
1
(x
7
/0)
∨
(x
2
/1)
(x
3
/1)
(x
3
/1)
(x
1
/1)
(x
2
/0)
∨
(x
3
/1)
(x
1
/0)
∨
(x
2
/1)
(x
7
/1)
(x
3
/1)
s
1
s
2
s
3
s
4
(x
2
/0)
Рис. 5.21

Страницы