4. Конечные автоматы
Основные понятия
Логическая схема (автомат), значения выходных переменных которого определяется только комбинацией значений переменных на его входах в данный момент времени называется комбинационной схемой. Если состояние схемы зависит также и от предыдущих значений входных переменных, схему называют последовательностной. Оба типа схем, в которых входные и выходные переменные принимают значения из конечных алфавитов, объединяются под названием конечные автоматы.
Конечный
автомат М
определяется как система с конечным
входным алфавитом
,
конечным выходным алфавитом
,
конечным множеством состояний
и двумя характеристическими
функциями:
;
,
называемых соответственно функцией переходов и функцией выходов.
Работу автомата можно представить таблицей переходов, таблицей выходов, графом автомата или матрицей соединений.
В таблице переходов:
-
s() \ x()
0
1
2
3
0
3
2
1
3
1
3
2
1
3
2
3
2
2
3
3
3
0
0
1
левый столбец соответствует текущему состоянию автомата, верхняя строка – значение на входе автомата. Таблица определяет следующее состояние автомата при заданном входном воздействии и текущем состоянии автомата.
В таблице выходов:
-
s() \ x()
0
1
2
3
0
0
0
0
0
1
1
0
0
0
2
1
0
1
1
3
0
0
1
1
определяется значение на выходе автомата при заданном входном воздействии и текущем состоянии автомата.
Две указанные таблицы могут быть объединены в общую таблицу переходов, где определятся состояние автомата на следующем такте и его выход:
-
s() \ x()
0
1
2
3
0
3/0
2/0
1/0
3/0
1
3/1
2/0
1/0
3/1
2
3/1
2/0
2/1
3/1
3
3/0
0/0
0/1
1/1
Рис.15
Граф автомата, соответствующий приведенным таблицам представлен на рис.15. Состояния автомата представлены вершинами графа. Ребрам графа приписаны входное воздействие/выход автомата.
Матрица соединений, соответствующая автомату с графом рис.15 представлена ниже:
.
Задачи
Накопительный счетчик, на вход которого подаются двоичные цифры 0 и 1, подсчитывает по модулю 3 общее число поступивших на вход единиц. Перечислите входной и выходной алфавиты, а также определите множество состояний.
а) Запишите таблицу переходов соответствующего конечного автомата.
б) Постройте граф автомата.
в) Запишите матрицу соединения автомата.
На основании графа рис.16 определите выходную последовательность и смену состояний автомата при начальном состоянии 3 и входной последовательности:
а) (0 1 2 3 3 0 1 2);
б) (2 0 1 3 2 0 0 2);
в) (3 1 0 0 2 3 0 2 1 1);
г) (2 3 0 1 0 3 2 1 1);
д) (3 3 2 0 1 0 0 2 1).
Постройте матрицу переходов и матрицу соединений для автомата
а) Рис.17.
б) Рис.18.
Рис.16 Рис.17 Рис.18