Определение абстрактного автомата

Абстрактный автомат является математической моделью дискретного управляющего устройства. Он задается множеством из шести элементов:

S={A, Z, W, a₁}, где

А={a₁,…,a_m,…,a_M}-множество состояний (алфавит состояний);

Z={z₁,…,z_f,…,z_F}-множество входных сигналов (входной алфавит);

W={w₁,…,w_g,…,w_G}-множество выходных сигналов (выходной алфавит);

-функция переходов, реализующая отображение множества

D_dÍA´Z в А (а_s= ;

- функция выходов, реализующая отображение множества

на ;

a₁ÎA – начальное состояние автомата.

Автомат называется конечным, если конечны множества A, Z и W.

Автомат называется полностью определенным, если , то есть область определения функций и совпадает со множеством всевозможных пар вида (a_m, z_f).

У частичного автомата функции или определены не для всех пар (a_m, z_f)ÎA´Z .

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

Z={z₁,…,z_F} W={w₁,…,w_G}

А={a₁,…,a_m}

Абстрактный автомат имеет один входной и один выходной канал. В каждый момент t=0, 1, 2,… дискретного времени автомат находится в определенном состоянии a(t)ÎA. При t=0 он всегда находится в нормальном состоянии а(0)=а₁. В момент t, будучи в состоянии a(t), автомат способен воспринять на входном канале сигнал z(t)ÎZ и выдать на выходном канале сигнал w(t)=l(a(t),z(t)), переходя в состояние а(t+1)=d(a(t),z(t)), a(t)ÎA, w(t)ÎW.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z во множество слов выходного алфавита W.

На практике наибольшее распространение получили автоматы Милии Мура.

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t),z(t)), t = 0, 1, 2, …

Закон функционирования автомата Мура:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t)), t = 0, 1, 2,…