Задание цифровых автоматов

Цифровой автомат считается заданным, если известны следующие параметры:

1) Множество состояний автомата .

2) Входной алфавит .

3) Выходной алфавит .

4) Функции переходов между состояниями и функции выходов.

5) Начальное состояние.

Задание ЦА возможно путем словесного описания его работы с последующим применением специальных формализованных способов описания, например, регулярных выражений. Далее выполняется переход к табличному или графовому представлению автомата.

Функционирование управляющего микропрограммного автомата может быть определено таблицей или графом переходов, полученным по размеченной схеме алгоритма его работы. Таким образом, для задания автомата по схеме алгоритма необходимо выполнить ее разметку в соответствии с типом задаваемого автомата.

Для автомата Мили разметка должна осуществляться следующим образом.

Все операторные вершины должны быть отмечены символами y₁, y₂, …, y_m. Одинаковые операторные вершины отмечаются одинаковыми символами y_i.

Все условные вершины отмечаются символами x₁, x₂, …, x_n. Одинаковые операторные вершины отмечаются одинаковыми символами X_i.

Выходы операторных вершин отмечаются символами внутренних состояний автомата a₁, a₂, …, a_z.

Для автомата Мура разметка выполняется аналогично за исключением символов состояний b₁, b₂, …, b_l, которыми отмечаются операторные вершины схемы.

По окончании выполнения алгоритма автоматы обоих типов должны возвращаться в исходное состояние.

Переходы автомата из состояния в состояние осуществляются под воздействием входных сигналов, соответствующих выполнению или невыполнению условия x_i. Невыполнению условия соответствует инверсное значение переменной x_i, выполнению условия – прямое значение переменной. При выполнении или невыполнении нескольких условий одновременно переход осуществляется под воздействием сигнала, представляемого конъюнкцией соответствующих прямых или инверсных значений переменных.

Рассмотрим пример. На рис. 5.7 изображена схема алгоритма, размеченная для задания автомата Мили и автомата Мура. Составим соответствующие им графы переходов (рис. 5.8, 5.9).