Теория автоматов Определение автомата и его разновидности. Таблицы и графы переходов и выходов. Подавтоматы. Теорема о приведенном автомате Операции с автоматами Преобразование автомата Мили в автомат Мура и автомата Мура в автомат Мили

1. 
   техническом,
   
2. 
   математическом.
   

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

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

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

ЦА считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y. Конечный автомат можно поставить в соответствие такому устройству, как компьютер. Компьютер перерабатывает поступающие входные данные в выходные данные (результат), но этот результат соответствует не только входным данным, но и текущему состоянию компьютера, т.е. тем данным, которые хранятся в памяти компьютера, например, результаты предыдущих вычислений, программы вычислений.

Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.

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

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

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

Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i-того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.

Понятие «состояние» используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и/или слов выходного языка от символов и/или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата sS и для каждого символа xX в момент дискретного времени [] на выходе устройства генерируется символ yY. Эту зависимость определяет функция выходов автомата . Для каждого текущего состояния автомата sS и для каждого символа xX в момент дискретного времени [] автомат переходит в очередное состояние sS. Эту зависимость определяет функция переходов автомата . Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (s_1[[1]s₂[2]s₃[3]...) и последовательности выходных символов (y₁[1]y₂[2]y₃[3]...), которые для последовательности символов (x₁[1]x₂[2]x₃[3]...) разворачиваются в моменты дискретного времени = 1,2,3,.... В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках - последовательности символов алфавитов X, Y и S.

Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и S, а операциями - две функции  и :

 M =  X; Y; S;  (1.1)

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

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

: SX) SY). (1.2)

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

(1.3)

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

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

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

…………………………………………….. (1.4)

[n]= ((s[1];x₁[1])(s[2];x₂[2]) ... (s[n];x_n[n])) =

= ((s[1];x₁[1])(s[1];(x₁[1]x₂[2])) ... (s[1];(x₁[1]x₂[2] ... x_n[n])));

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

= ((s;x₁)(s;(x₁x₂))...(s;(x₁x₂...x_n)))=((s;)). (1.5 )

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

 = ((x₁x₂...x_n-1)x_n) =(x_n), (1.6)

где  =(x₁x₂...x_n-1) - "голова" слова 

x_n - "хвост" слова .

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

= (s; ) = ((s; );x_n). (1.7)

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

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

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

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

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

s[n+1] = (s[n];x_n[n]) = (... ((((s[1];x₁[1]);x₂[2]);x₃[3]);...x_n-1[n-1]);x_n[n]),

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

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

s[n+1] = (... ((((s;x₁);x₂);x₃)...x_n-1);x_n). (1.9)

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

s[n+1] = ((s; );x_n). (1.10 )

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

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

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

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

M =  X;Y;S;;s₀ (1.11)

Последовательность символов в слове  и последовательность состояний автомата s однозначно определяются начальным состоянием автомата s=s₀ и последовательностью символов во входном канале . Поэтому отображение входного слова на выходное слово чаще называют автоматным отображением, то есть = М(s₀;), а М – автоматным оператором.

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

1. 
   входное и выходное слова имеют одинаковую длину (свойство сохранения длины);
   

Для описания (задания) ЦА используются разнообразные средства, называемые языками, которые делятся на начальные и автоматные языки. Поскольку языки базируются на алфавитах, то применительно к ЦА множество Х трактуется в качестве входного алфавита, множество Y - выходного алфавита, а множество S - внутреннего алфавита. Как и для других объектов, для автоматов используются разные таблицы, матрицы, графы.

Наиболее общее при выработке выходных сигналов, формировании новых состояний под действием входных сигналов отражается законом функционирования автомата [4, 12]:

s(t)=  (s(t-1), x(t)),

В формулах используются обозначения:

t - данное автоматное время, t-1 - предыдущее автоматное время,  - оператор формирования данного состояния s,  - оператор формирования данного выходного сигнала y, х - входной сигнал.

Видно, что данное состояние s(t) зависит от предыдущего состояния s(t-1) и входного сигнала в данный момент времени, что выходной сигнал в данный момент времени так же определяется предыдущим состоянием и входным сигналом в данный момент времени.

Автомат задан, если заданы:

1. 
   Конечное множество входных сигналов, заданных с помощью входного алфавита X={x₁, x₂,…, x_m}
   
2. 
   Конечное множество выходных сигналов, заданных с помощью выходного алфавита y={y₁, y₂ ,..., y_n}
   
3. 
   Конечное множество состояний автомата заданного с помощью алфавита S={s₁,s₂,...s_m}
   
4. 
   Начальное состояние автомата
   
5. 
   Функция выходов, определяющая зависимость выходного сигнала и состояния автомата y[kt]=f_в(U[kt], a[kt]) где t – длительность такта k – номер такта. Конечный автомат существует в конечном (дискретном) времени.
   
6. 
   Функция переходов
   

Таким образом, в определении конечного автомата фигурирует три множества и две функции M={X, Y, S, f_в, f_п}

Функция перехода f_п:X*S_S Функция выхода f_в:X*S_Y

Операторы, описывающие работу автомата, обычно задают таблицей переходов и таблицей выходов.

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

К примеру, рассмотрим таблицы переходов и выходов некоторого автомата.

Входной сигнал	Состояние
	a0	a1	a2	a3
x1	a1	a2	a3	a3
x2	a0	a0	a0	a0

Таблица выходов автомата

Входной сигнал	Состояние
	a0	a1	a2	a3
x1	y2	y2	y1	y2
x2	y2	y2	y2	y3

В клетку таблицы переходов, находящуюся на пересечении столбца с буквой а_i и строки с буквой x_j, записывается состояние автомата, в которое он переходит из состояния а_i при подаче на вход сигнала x_j. В аналогичную клетку таблицы выходов записывается выходной сигнал y_i, который формируется автоматом при таком переходе.

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

Таблица переходов и выходов автомата

Выходной сигнал	Cостояние
	a0	a1	a2	a3
x1	a1 y2	a2 y2	a3 y1	a3 y2
x2	a0 y2	a0 y2	a0 y2	a0 y3

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

Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит.

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