6.1. Абстрактный автомат

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

Слова входного языка можно представить символами множества X={x₁,x₂,...x_n}, который называют входным алфавитом, а слова выходного языка - символами множества Y={y₁,y₂,...y_p}, который называют выходным алфавитом.

Множество состояний автомата Q={q₁,q₂,...q_m} называют алфавитом состояний. Понятие "состояние" автомата используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов от символов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата qQ и для каждого символа входного языка xX в момент дискретного времени [] на выходе устройства генерируется символ yY. Эту зависимость определяет функция выходов автомата - . Для каждого текущего состояния автомата qQ и для каждого символа xX в момент дискретного времени [] автомат переходит в очередное состояние qQ. Эту зависимость определяет функция переходов автомата - .

Функционирование автомата есть последовательность состояний автомата (q_1[[1]q₂[2]q₃[3]...) и выходных символов (y₁[1]y₂[2]y₃[3]...) под влиянием последовательности символов на входе автомата (x₁[1]x₂[2]x₃[3]...). Каждый символ входной последовательности считывается в дискретный моменты времени []=1, 2, 3,...Поэтому в прямых скобках. указывают моменты дискретного времени, которые называют тактами,

Математическая модель конечного автомата есть

M =X; Y; Q; ; 

где X={ x1, x2,...xn }	-	- множество символов входного алфавита;
Y={ y1, y2, ..yp }	-	- множество символов выходного алфавита;
Q={q1, q2,...qm}	-	- множество символов состояний автомата;
 (QX) Q	-	- функция переходов автомата для отображения пары (q; x) текущего момента времени [] в состояние q очередного момента времени [+1];
 (QX) Y	-	- функция выходов автомата для отображения пары (q; x) текущего момента времени [] в символ y выходного канала этого же момента времени [].

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

, : (QX) (QY).

Функционирование автомата в дискретные моменты времени может быть описано системой рекуррентных соотношений:

Если на входе автомата слово  = (x₁x₂x₃...x_), то, считывая последовательно символы этого слова, на выходе автомата генерируется последовательность символов слова  по схеме:

[1]=((q[1]; x₁[1]));

[2]=((q[1]; x₁[1]) (q[2]; x₂[2])) = ((q[1]; x₁[1])(q[1]; (x₁[1]x₂[2])));

……………………………………………..............................................

[]=((q[1];x₁[1])(q[2];x₂[2])...(q[s];x_[])) =

= ((q[1];x₁[1])(q[1];(x₁[1]x₂[2]))...(q[1];(x₁[1]x₂[2] ... x_[])));

Так как на каждом i-ом такте к слову длины (i-1) приписывается справа очередной символ (q[1]; (x₁[1]x₂[2]...x_i[i])), то последовательность символов выходного слова можно записать так:

= ((q;x₁)(q;(x₁x₂))...(q;(x₁x₂...x_s)))=((q; )).

Если считывание символов входного слова  выполняется последовательно слева направо, то всегда найдется такая последовательность (x₁x₂...x_s-1)=, для которой  = ((x₁x₂...x_s-1)x_s) =(x_s), где  =(x₁x₂...x_s-1) –"голова" слова , а x_s –“хвост" слова .

Поэтому если входное слово  = (x_s), то выходное слово  можно записать так

=(q;  ) = ((q; );x_s

Это означает, что последний символ слова  есть результат работы автомата, начавшего работу в состоянии q и считавшего последний символ слова , но значение этого символа зависит от всей входной последовательности .

Длина выходного слова всегда равна длине входного слова.

Изменение состояний автомата для последовательности символов слова  = (x₁x₂x₃...x_s) может быть описано следующей схемой:

q[2] = (q[1];x₁[1]);

q[3] = (q[2];x₂[2]) = ((q[1];(x₁[1]);x₂[2]));

............................................................................................

q[+1] =(q[s];x_[])=(..( ( (q[1];x₁[1]);x₂[2]);..x_-1[-1]);x_ []),

где q[1] - начальное состояние автомата.

Так как за один такт автомат считывает один символ входного слова, то в последовательности состояний автомата можно не указывать номер такта, т. е. описывать так:

q[+1] = (... ((((q;x₁);x₂);x₃)...x_-1);x_).

Если входное слово  =(x_), то изменение состояния автомата может быть описано так:

q[+1] = ((q, );x_).

Это означает, что q[+1] есть последнее состояние автомата, начавшего работу в состоянии q и считавшего последний символ слова  в момент дискретного времени .

Если функции переходов и выходов однозначно определены для каждой пары (q; x)(QX), то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определенным.

Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.

Если у автомата задано начальное состояние q=q₀Q, в котором он находится всегда до приема первого символа входного слова, то автомат называют инициальным.

В этом случае модель автомата записывают так:

M=X; Y; Q; ; ;q₀.

Последовательность символов в слове  и последовательность состояний автомата q однозначно определяются начальным состоянием автомата q=q₀ и последовательностью символов во входном слове .

Отображение входного слова  на выходное слово  называют автоматным отображением, то есть =М(q₀; ), а М называют автоматным оператором.

Автоматное отображение обладает свойствами:

• входное и выходное слова имеют одинаковую длину;

• y_i-ый символ выходного слова зависит от всей последовательности символов входного слова, до x_i-го включительно.