Модели дискретных систем. Конечные автоматы

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

Абстрактно конечный автомат (англ. finite automat) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством Х входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом, или алфавитом состояний); начальным состоянием z₀ , z₀ Î Z;функцией переходов φ(z, х); функцией выходов ψ(z, х).

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

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

Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние z₀,подавать в некоторой последовательности буквы входного алфавита х(0), х(1), х(2), ..., т.е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у(0), у(1), у(2), ..., образуя выходное слово.

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

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

у(t) = ψ[z(t), x(t)], t = 0, 1, 2,...;

для F-автомата второго рода

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

y (t) = ψ[z(t), x(t – 1)], t = l, 2, 3,...

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

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

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

Таким образом, все указанные уравнения, полностью задающие F-автомат, являются частным случаем уравнений, задающих детерминированную систему S, на единственный вход которой поступает дискретный сигнал Х. Поэтому рассмотренные конечные автоматы являются детерминированными.

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

у(t) = ψ [х(t)], t = 0, 1, 2, ....

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

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

АсинхронныйF-автоматсчитывает входной сигнал непрерывно. Реагируя на достаточно длинный входной сигнал постоянной величины х, он может, как следует из вышеприведенных уравнений, несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в устойчивое, которое уже не может быть изменено данным входным сигналом. Чтобы задать конечный F-автомат, необходимо описать все элементы множества F = <Z, Х, Y, φ, ψ, z₀>, т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние z₀, в котором автомат находился в момент времени t = 0. Наиболее часто используются следующие способы задания работы F-автоматов: табличный, графический и матричный.

Простейший табличный способ задания конечного автомата основан на использовании таблиц переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. При этом обычно первый слева столбец соответствует начальному состоянию z₀. На пересечении i-й строки и k-го столбца таблицы переходов помещается соответствующее значение φ(z_k, х_i) функции переходов, а в таблице выходов – соответствующее значение ψ(z_k, х_i) функции выходов. Для F-автоматаМура обе таблицы можно совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием z_k автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию (согласно уравнению) выходной сигнал ψ(z_k). Описание работы F-автоматаМили дано таблицей 1 переходов φ и выходов ψ.

Таблица 1

Таблица переходов φ и выходов ψ для F-автомата Мили

Описание F-автоматаМура дано таблицей переходов 2.

Таблица 2

Таблица переходов для F-автомата Мура

Примеры табличного способа задания работы F-автоматаМили F1 с тремя состояниями, двумя входными и двумя выходными сигналами приведены в табл. 3, а F-автоматаМура F2 – в табл. 4. ­­­

Таблица 3

F-автомат Мили

Таблица 4

F- автомат Мура

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

Рис. 2.2. Граф автомата Мили F1, соответствующий таблице 3

Для автомата Мура аналогичная разметка графа такова: если входной сигнал х_k, действуя на некоторое состояние автомата, вызывает переход в состояние z_j, то дугу, направленную в z_j и помеченную х_k,дополнительно отмечают выходным сигналом y = ψ(z_j, х_k) (рис. 2.3).

Рис. 2.3. Граф автомата Мура F2, соответствующий таблице 4

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

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

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

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

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

Рассмотрим таблицу переходов и граф асинхронного конечного автомата. Для F-автомата состояние z_k называется устойчивым, если для любого входа х_iÎ Х, для которого φ(z_k, х_i)= z_k, имеет место ψ(z_k, х_i)=y_k. Таким образом, F-автомат называется асинхронным, если каждое его состояние z_kÎ Zустойчиво.

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

Рис. 2.4. Граф асинхронного автомата Мура

Пример 2. Рассмотрим асинхронный F-автоматМура, который описан табл. 5 и приведен на рис. 2.4. Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние z_k стоит на пересечении строки х_i и столбца z_s (s≠k), то это состояние z_k обязательно должно встретиться в этой же строке в столбце z_k. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине z_k должна быть петля, отмеченная символами тех же входных сигналов. Анализ табл. 3 и 4 или рис. 2.2и 2.3 показывает, что представленные там F-автоматы F1 и F2 являются синхронными.

Таблица 5

Пример 3. Рассмотрим совсем простой пример описания конечного автомата, предназначенного для торговли напитками. Допустим, что чашка чая стоит 10 руб., а чашка кофе – 50 руб. Пусть автомат может принимать денежные купюры достоинством 10 и 50 рублей. Это значит, что входной алфавит автомата состоит из двух сигналов: x₁={10 руб.} и x₂={50 руб.}. Пусть автомат может выдавать чай или кофе. Это означает, что выходной алфавит автомата состоит из двух сигналов: y₁={чай} и y₂={кофе}. Наконец, пусть внутренних состояний такого автомата тоже будет только два: z₁={готов к выдаче чая} и z₂={готов к выдаче кофе}. Предположим, что подачи в приемное отверстие купюр достоинством 10 руб. или 50 руб. являются непосредственно управляющими входными сигналами, сразу вызывающими изменение состояния автомата и выдачу напитков, так что не требуется дополнительно нажимать никакие кнопки. Такой автомат в упрощенном виде изображен на рис. 2.5. На рисунке никак не отражен процесс приготовления кофе или чая (размельчение зерен, нагрев воды, заваривание и т.д.), а только условно показаны две емкости, из которых осуществляется разлив. В положении, показанном на рисунке, автомат готов к разливу кофе, т.е. он находится в состоянии z₂.

Рис. 2.5. Автомат для продажи чая и кофе

Граф, соответствующий работе рассмотренного автомата для продажи напитков, показан на рис. 2.6. Если в момент подачи на вход купюры 10 руб. (x₁) он уже находился в состоянии готовности к выдаче чая (z₁), то он сразу выдаст чай (y₁) – этому соответствует петля из состояния z₁. Если же автомат находился в этот момент в состоянии готовности к выдаче кофе (z₂), то сначала он перейдет в состояние z₁, а затем сразу выдаст чай – этому соответствует дуга, ведущая из состояния z₂ в состояние z₁ . Аналогично все происходит при подаче на вход купюры 50 руб. (x₂). Если автомат был в состоянии z₂, то он сразу выдаст кофе (y₂), а если был в состоянии z₁, то сначала перейдет в z₂ , а затем выдаст кофе. Очевидно, что этот автомат детерминированный, асинхронный.

Рис. 2.6. Граф автомата для продажи напитков из примера 3

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

Кроме конечных автоматов, которые относятся к дискретно-детерминированным моделям, или F-схемам, существуют также и вероятностныеавтоматы, или P-схемы (от англ. probabilistic automat), которые относятся к дискретно-стохастическим моделям. В вероятностных автоматах переходы из одного состояние в другое и появление сигналов на выходе могут происходить с вероятностями, которые определяются заданными функциями распределения.

Вопросы к разделу 2.2

1. Какие системы называют гладкими?
2. Чем характеризуются F-автоматы?
3. Является ли конечным автоматом автомат Калашникова?
4. Чем отличаются автоматы Мили от автоматов Мура?
5. Сколько состояний имеют комбинационные схемы?
6. Сколько входов и сколько выходов имеет абстрактный конечный автомат?
7. Как определить по виду графа, какой автомат он описывает: синхронный или асинхронный?
8. Что представляют собой P-автоматы?