Конечные автоматы

Особенности дискретно-детерминированных моделей, используемых при формализации процесса функционирования систем, рассмотрим на примере применения в качестве математического аппарата тео­рии автоматов. На основе этой теории система представляется в виде автомата, перерабатывающего дискретную информацию и меняю­щего свои внутренние состояния лишь в допустимые моменты вре­мени[11].

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему, характеризую­щуюся шестью элементами: конечным множеством Х входных сиг­налов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множествомZ внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z₀, z₀ÎZ ; функцией переходов j(z,x); функцией выходов y(z,x). АвтоматF=<Z, X, Y, j, y, z₀> функционирует в дискретном времени, моментами которого являются такты, т. е. примыкающие друг к другу равные интервалы времени, каждому из которых соот­ветствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t-му такту при t=0, 1, 2,…, через z (t), x(t), y(t). При этом, по условию, z(0)=z₀, a z(t)ÎZ, x(t)ÎX, y(t)ÎY.

Абстрактный конечный автомат имеет один входной и один вы­ходной каналы. В каждый момент t=0, 1, 2,... дискретного вре­мени автомат находится в определенном состоянии z(t) из мно­жества Z состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии z(0)=z₀. В мо­мент t, будучи в состоянии z(t), автомат способен воспринимать на входном канале сигнал x(t)ÎX и выдавать на выходном канале сигнал y(t)=y[z(t),x(t)], y(t)ÎY, переходя в состояние z(t+1)=j[z(t),x(t)], z(t)ÎZ. Абстрактный конечный авто­мат реализует некоторое отображение множества слов входного алфавита Х на множество слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в на­чальное состояние z₀, подавать в некоторой последовательности буквы входного алфавита x(0), x(1), x(2),…, т. е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавитаy(0), y(1), y(2),…,образуя вы­ходное слово.

Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t-м такте на вход автомата, находяще­гося в состоянии z(t), подается некоторый сигнал х (t), на кото­рый он реагирует переходом в (t+1)-м такте в новое состояние z(t+1) и выдачей некоторого выходного сигнала. Сказанное выше можно описать следующими уравнениями: для конечного автомата первого рода, называемого также автоматом Мили,

z(t+1)=j[z(t),x(t)], t=0,1,2,..,

y(t)=y[z(t),x(t)], t=0,1,2,…;

для конечного автомата второго рода

z(t+1)=j[z(t),x(t)], t=0,1,2,..,

y(t)=y[z(t),x(t-1)], t=1,2,3,…

Автомат второго рода, для которого

y(t)=y[z(t)], t=0,1,2,…,

то есть функция выходов не зависит от входной переменной х (t), называется автоматом Мура.

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

y(t)=y[x(t)], t=0,1,2,….

Эта функция называется булевой, если алфавиты Х и Y, кото­рым принадлежат значения сигналов x и y, состоят из двух букв.

По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные. В синхронных автоматах моменты времени, в которые автомат «считывает» входные сигналы, определяются принудительно синхронизирующи­ми сигналами. После очередного синхронизирующего сигнала с учетом «считанного» происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение вход­ного сигнала. Таким образом, реакция автомата на каждое значе­ние входного сигнала заканчивается за один такт, длительность которого определяется интервалом между соседними синхронизи­рующими сигналами.

Асинхронный автомат считывает входной сигнал непрерывно, и поэтому, реагируя на достаточно длинный входной сигнал постоянной величины х(t)=const, он может несколько раз изменять состояние, выдавая соот­ветствующее число выходных сигналов, пока не перейдет в устой­чивое, которое уже не может быть изменено данным входным сигналом.

Чтобы задать конечный автомат, необходимо описать все эле­менты F=<Z, X, Y, j, y, z₀ >, т. е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов. Причем среди множества состояний необходимо выделить состоя­ние z₀, в котором автомат находился в момент времени t=0. Суще­ствуют несколько способов описания работы конечных автоматов, но наибо­лее часто используются табличный, графический и матричный.

Простейший табличный способ задания конечного автомата основан на использовании таблиц переходов и выходов, строки ко­торых соответствуют входным сигналам автомата, а столбцы - егосостояниям. При этом обычно первый слева столбец соответствует начальному состоянию z₀. На пересечении i-й строки и k-ro столбца таблицы переходов помещается соответствующее значение j(z_k,x_i) функции переходов, а в таблице выходов - соответствующее значение y(z_k,x_i) функции выходов. Для конечного автомата Мура обе таблицы можно совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием z_k автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию выходной сигнал y(z_k). Описание конечного автомата Мили таблицами переходов j и выходов y иллюстрирует табл.5.1,а описание автомата Мура таблицей переходов - табл. 5.2.

Таблица 5.1. Таблицы переходов и выходов конечного автомата Мили

Таблица 5.2. Таблица переходов конечного автомата Мура

Пример 5.1.Примеры табличного способа задания конечного автомата Мили F1 с тремя состояниями, двумя входными и двумя выходными сигна­лами приведены в табл. 5.3, а для конечного автомата Мура F2 - в табл. 5.4.

Таблица 5.3. Табличное описание автомата Мили

Таблица 5.4. Табличное описание автомата Мура

При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал x_k вызывает пе­реход из состояния z_i в состояние z_j, то на графе автомата дуга, соединяющая вершину z_i с вершиной z_j, обозначается x_k. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производится так: если входной сигнал x_k действует на состояние z_i, то, согласно сказанному, получается дуга, исходя­щаяиз z_iи помеченная x_k; эту дугу дополнительно отмечают выходным сигналом y(t)=y(z_j,x_k). Для автомата Мура анало­гичная разметка графа такова: если входной сигнал x_k, дейст­вуя на некоторое состояние ав­томата, вызывает переход в со­стояние z_j, то дугу, направлен­ную в z_j, помечают x_k, а вершину z_j дополнительно отмечают выход­ным сигналом y(t)=y(z_j).

Заданные ранее таблицами конечные автоматы Мили F1 и Мура F2 приведены на рис. 5.1.

При решении задач моделирования систем часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица , строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент c_ij=x_k/y_s, стоящий на пересечении i-й строки и j-ro столбца, в случае автомата Мили соответствует входному сигналу x_k, вызывающему переход из состояния z_i в со­стояние z_j, и выходному сигналу y_s, выдаваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица сое­динений имеет вид

.

Если переход из состояния z_i в со­стояние z_j происходит под действием нескольких сигналов, элемент матрицы c_ij представляет собой множество пар «вход-выход» для этого перехода, соединен­ных знаком дизъюнкции.

Для автомата Мура элемент c_ij равен множеству входных сигналов на переходе (z_i,z_j), а выход описывается вектором вы­ходов

,

i-я компонента которого - выходной сигнал, отвечающий состоя­нию z_i.

Пример 5.2. Для рассмотренного выше автомата Мура F2 запишем матрицу соединений и вектор выходов:

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

Рассмотрим вид таблицы переходов и графа асинхронного ко­нечного автомата. Для конечного автомата состояние z_k называется устой­чивым, если для любого входа x_iÎX, для которого j(z_k,x_i)= z_k, имеет место y(z_k,x_i)=y_k. Таким образом, конечный автомат называется асинхронным, если каждое его состояние z_iÎZ устойчиво.

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

Пример 5.3. Рассмотрим асинхронный автомат Мура, который описан табл. 5.5 и приведен на рис. 5.2. Очевидно, что если в таблице переходов асин­хронного автомата некоторое состояние z_k стоит на пересечении строки x_iи столбца z_s (s¹k), то это состояние z_k обязательно должно встретиться в этой же строке в столбце z_k. В графе асинхронного автомата, если в некоторое со­стояние имеются переходы из других состояний под действием каких-то сигна­лов, то в вершине z_k должна быть петля, отмеченная символами тех же входных сигналов. Анализ табл. 5.3 и 5.4 или рис. 5.1 показывает, что представ­ленные там автоматы F1 и F2 являются синхронными.

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