В наиболее общем случае автоматами называют технически или программно реализованные модули, предназначенные для переработки поступающей информации. Конечный автомат — это модуль, имеющий конечное число возможных состояний и функционирующий в дискретном времени. В данной работе конечный автомат изучается как абстрактное алгоритмическое устройство, предназначенное для обработки слов фиксированного входного алфавита. Считаем, что обработку произвольного слова во входном алфавите автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние; состояние, в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины l автомат работает l тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.
Целью данной работы является исследование и логическое проектирование конечного частично определенного автомата.
Автомат будем описывать с помощью таблицы соединений, а для наглядности использовать графы.
При табличном описании можно задавать две таблицы, первая из которых раскрывает функции перехода, а вторая — функцию выходов .
Число строк таблиц равно числу состояний автомата, а число столбцов таблиц равно числу символов входного алфавита. В клетки первой таблицы записываются значения очередных состояний для каждой пары. В клетки второй таблицы записываются выходные символы для каждой пары .
Анализ поведения автомата проводится с помощью графа. Его вершинами являются элементы множества Q, т. е. состояния автомата.
Основными этапами проектирования конечного автомата являются:
кодирование алфавитов;
выбор комбинационного автомата;
выбор элементов двоичной задержки;
формирование функции выхода и переходов;
построение логической схемы структурного автомата.
В качестве элементов двоичной задержки в работе используются JK-триггеры. Триггер представляет собой автомат Мура, обладающий двумя устойчивыми состояниями «0» и «1». Система функции переходов триггера является полной, т. е. для любого состояния существует входной сигнал, переводящий триггер в другое состояние.
