Канонический синтез цифровых автоматов

Математическая модель цифрового устройства представляется в виде абстрактного автомата (АА). АА задается множеством:

S={A, Z, W, δ, λ, a₀}, где

А – множество состояний автомата;

Z – множество входных сигналов (входной алфавит);

W – множество выходных сигналов автомата (выходной алфавит);

δ – функция переходов автомата;

λ – функция выходов;

a₀ – исходное состояние автоматов.

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

Существует два основных способа задания абстрактного автомата:

1. табличный;

2. графический.

На практике наиболее широко распространены две модели автоматов:

1. Автомат Мили

Функция перехода – ;

Функция выходных сигналов – .

2. Автомат Мура

Функция перехода – ;

Функция выходных сигналов – .

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

Состояние автомата – память о входных сигналах, поступивших на вход автомата в предыдущий момент времени. Состояние хранит трассу функционирования автомата.