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

Теория автоматов

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

Операции с автоматами

Преобразование автомата Мили в автомат Мура и автомата Мура в автомат Мили. Эквивалентность автоматов. Различимость состояний автоматов. Минимизация автоматов. Синтез автоматов. Распознающие автоматы

Автомат — система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации Термин "автомат" используется в двух аспектах:

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 в момент дискретного времени [t] на выходе устройства генерируется символ yÎY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] автомат переходит в очередное состояние sÎS. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (s_1[[1]s₂[2]s₃[3]...) и последовательности выходных символов (y₁[1]y₂[2]y₃[3]...), которые для последовательности символов (x₁[1]x₂[2]x₃[3]...) разворачиваются в моменты дискретного времени t = 1,2,3,.... В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках - последовательности символов алфавитов X, Y и S.

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

M = á X; Y; S; y; jñ, (1.1)

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

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

(y;j): (SÄX) ® (SÄY). (1.2)

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

(1.3)

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

b[1]=(j(s[1];x₁[1]));

b[2]=(j(s[1];x₁[1])j(s[2];x₂[2])) = (j(s[1];x₁[1])j(s[1];(x₁[1]x₂[2])));

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

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

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

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

b = (j(s;x₁)j(s;(x₁x₂))...j(s;(x₁x₂...x_n)))=(j(s;a)). (1.5)

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

a = ((x₁x₂...x_n-1)x_n) =(gx_n), (1.6)

где g =(x₁x₂...x_n-1) - "голова" слова a;

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

Поэтому если входное слово a = (gx_n), то выходное слово b можно записать так:

b = j(s;a) = j(y(s;g);x_n). (1.7)

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

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

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

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

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

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

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

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

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

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

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

s[n+1] = y(y(s;g);x_n). (1.10)

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

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

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

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

M = á X;Y;S;y;j;s₀ñ, (1.11)

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

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

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

2) y_i-ый символ выходного слова зависит от всей последовательности символов входного слова, до x_i-го включительно; кроме того если a=a₁a₂, то b=b₁b_2..

Задание конечного автомата:

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

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

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

y (t)= l (s(t-1), x (t)).

Как видно, закон функционирования представляет собой совокупность двух функций: функции перехода d и функции выхода l.

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

t - данное автоматное время, t-1 - предыдущее автоматное время, d - оператор формирования данного состояния s, l - оператор формирования данного выходного сигнала 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

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

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

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

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

1) по закону функционирования ЦА делятся на автоматы 1-го рода (автоматы Мили) и ЦА 2-го рода. Последние автоматы в случае, когда нет явной зависимости от входных сигналов x (t), являются автоматами Мура. Видимо, целесообразнее по первому критерию автоматы делить на автоматы Мили и Мура;

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

(1.12)

(1.13)

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t].

Рис. 1.3. Функциональная схема автомата Мили.

В автомате Мура функция j определяет значение выходного символа только по одному аргументу - состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:

(1.14)

(1.15)

Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t].

Рис. 1.4. Функциональная схема автомата Мура.

2) по конечности множеств X, Y, и S автоматы бывают конечными и бесконечными. Может быть, данный критерий стоит трактовать как критерий по мощности ЦА;

3) по объему памяти автоматы делятся на автоматы с памятью (последовательностные автоматы) и автоматы без памяти (логические комбинационные схемы);

4) по степени раскрытия структуры автоматы бывают абстрактными автоматами (детали структуры не раскрыты) и структурными автоматами (раскрыты детали структуры);

5) по отношению между автоматами среди автоматов можно выделить подавтоматы, надавтоматы. Если, например, известно, что ЦАА < ЦАВ, то автомат А является подавтоматом автомата В, а автомат В - надавтоматом автомата А;

6) по полноте используемых переходов автоматы делятся на полностью определенные автоматы и частично определенные автоматы;

7) по стабильности периода следования входных сигналов автоматы бывают синхронными автоматами (период следования входных сигналов- постоянная величина) и асинхронными автоматами (период - переменная величина);

8) по вероятности переходов автоматы делятся на детерминированные (не вероятностные) и недетерминированные (вероятностные) автоматы;

9) при нулевой мощности множества внутренних состояний (| S |= 0) автомат называется автономным, при | Y | = 0 - автоматом без выхода. Если среди состояний автомата выделяется начальное состояние s0, то автомат называется инициальным;

10) по применению автоматы можно разделить на автоматы:

а) промышленные (сварочные, кузнечно-прессовые, литейные, строительные, транспортные, упаковочные роботы, контрольные, диагностические и др.);

б) сельскохозяйственные (доильные, раздаточные, уборочные и др.);

в) торговые (газетные, упаковывающие, взвешивающие и др.);

г) учебные (обучающие, тестирующие, моделирующие, демонстрирующие и др.);

д) медицинские (искусственные органы, хирургические, диагностирующие, дыхательные, тренирующие и др.);

е) информационные (видеомагнитофоны, системы "вопрос - ответ" и др.).

Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

(1.16)

Рис.1. 5. Функциональная схема С-автомата.

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

Пусть X=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.17)

(1.18)

Функциональная схема автомата приведена на рис.1.6.

Рис.1.6. Функциональная схема порождающего автомата.

Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.

Пусть Y=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.19)

q[t+1] = y(q[t];x[t]); (1.20)

Функциональная схема автомата приведена на рис.1.7.

Рис. 1.7. Функциональная схема распознающего автомата.

Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (q_i[t];x_i[t]) и перевод автомата в заключительное состояние q_k. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.

Пусть Q=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.21)

y[t] = j(x[t]); (1.22)

Функциональная схема автомата приведена на рис.8.

Рис. 1.8. Функциональная схема комбинационного автомата.

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

Автоматы, выполняющие роль "0" и

"1" в алгебре автоматов. С - автомат

Любая алгебра должна иметь конструкции, выполняющие в ней роль "0" и "1". По аналогии с алгеброй алгоритмов роль "0" выполняет пустой автомат (ноль-автомат), ЦА0. Пустой автомат – это автомат, в котором запрещены всевозможные переходы. Естественно, что ЦАА \/ ЦА0 = ЦАА, ЦАА /\ ЦА0 = ЦА0.

Роль "1" возлагается на полный ЦА (ЦА1), в простейшем случае такой автомат представляет собой настраиваемое объединение рассматриваемых автоматов. Естественно, что ЦАА \/ ЦА1 = ЦА1, ЦАА /\ ЦА1 = ЦАА, дополнение ЦА1 = ЦА0, дополнение ЦА0 = ЦА1.