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

UptoLike

ВУЗ: 

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

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

Рубрика: 

199
будет переход в состояние 100. Обозначим его s
3
. И, наконец, вход-
ной символ
x
4
(11) пере-
водит автомат в состоя-
ние
101 (s
4
). Таким об-
разом, автоматная таб-
лица будет содержать
еще три столбца для со-
стояний
s
2
, s
3
, s
4
. Ана-
логичным способом проанализируем эти три новых столбца. В ре-
зультате получим еще четыре возможных состояния, а именно:
010
(s
5
), 011 (s
6
), 110 (s
7
) и 111 (s
8
). Анализ переходов из этих состояний
завершает построение функции переходов. Результат построения
функции переходов представлен в табл.
5.22.
Выход автомата будет иметь символ
u
2
,
если он находится в состояниях
{011, 111}. В
остальных случаях на выходе должен быть
символ
u
1
. Результат построения функции вы-
ходов приведен в верхней части автоматной
таблицы
(табл. 5.22). Заметим, что 1,2 и 5
столбцы, а также столбцы
3, 4 и 7 полностью
совпадают. Поэтому в каждом из данных мно-
жеств столбцов можно оставить только по одному, удалив остальные
столбцы и переобозначив оставшиеся состояния. В результате будем
иметь минимизированный вариант автоматной таблицы (табл.
5.23).
Можно доказать, что он соответствует явно минимальному автомату.
Таблица
5.22
u
1
u
1
u
1
u
1
u
1
u
2
u
1
u
2
0 0 0 0 0 1 0 1
s
1
s
2
s
3
s
4
s
5
s
6
s
7
s
8
000 001 100 101 010 011 110 111
00 x
1
000 000 010 010 001 001 010 010
01 x
2
001 001 011 011 000 000 011 011
10 x
3
100 100 110 110 001 001 110 110
11 x
4
101 101 111 111 100 100 111 111
Таблица 5.23
U u
1
u
1
u
2
u
2
s
1
s
2
s
3
s
4
x
1
s
1
s
1
s
1
s
1
x
2
s
1
s
3
s
1
s
3
x
3
s
2
s
2
s
2
s
2
x
4
s
2
s
4
s
3
s
4

Страницы