Абстрактный конечный автомат

Абстрактный конечный автомат – это математическая модель автомата, задаваемая множеством из семи элементов: , где

–множество внутренних состояний (алфавит состояний),

– начальное состояние конечного автомата,

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

– множество выходных сигналов 1-го рода

(выходной алфавит 1-го рода),

– множество выходных сигналов 2-го рода

(выходной алфавит 2-го рода),

– функция переходов.

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

– функция выходов 1-го рода, которая показывает, какой выходной сигнал 1-го рода сформируется на выходе 1-го рода в данный момент времени, если в данный момент времени автомат находился в состоянии a(t), а на вход поступал сигнал z(t): .

– функция выходов 2-го рода показывает, какой выходной сигнал 2-го рода сформируется на выходе 2-го рода в данный момент времени, если в

данный момент времени автомат находился в состоянии , а на вход поступал сигнал : .

В общем случае абстрактный автомат имеет 1 входной и 2 выходных канала. Такой автомат называют С-автоматом.

В каждый момент времени автомат находится в определенном состоянии . При - в начальном состоянии .

Автомат, находящийся в состоянии воспринимает входной сигнал , выдает на выход 1-го рода сигнал , выдает на выход 2-го рода сигнал и переходит в следующий момент времени в состояние .

.

Типы конечных автоматов.

Кроме рассмотренного выше С-автомата на практике получили распространение автоматы Мили и автоматы Мура.

Автомат Мили

Выходные сигналы автомата Мили - сигналы первого рода. Память автомата характеризуется множеством внутренних состояний автомата. Указывается (обязательно) состояние с которого автомат начинает работу - начальное состояние.

Алгоритм работы задается функцией переходов и функцией выходов первого рода:

.

Автомат Мура

Выходные сигналы автомата Мура - сигналы второго рода. Алгоритм работы задается функцией переходов и функцией выходов второго рода: