ДИСКРЕТНО-ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ

Лекция 9

(F-СХЕМЫ)

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

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

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

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

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

Z(t+1) = φ[z(t), х(t)], t=0, 1,2, (3.1)

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

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

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

у(t)=ψ[z(t), x(t-1)], t=1, 2, 3,.... (3.4)

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

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

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

Таким образом, уравнения (3.1) — (3.5), полностью задающие F-автомат, являются частным случаем уравнений (1.3) и (1.4), когда система S детерминированная и на ее единственный вход поступает дискретный сигнал X.

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

у (t)=ψ[x(t)], t=0,1,2, …

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

По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные. В синхронных F-автоматах моменты времени, в которые автомат «считывает» входные сигналы, определяются принудительно синхронизирующими сигна­лами. После очередного синхронизирующего сигнала с учетом «счи­танного» и в соответствии с уравнениями (3.1) — (3.5) происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сиг­нала. Таким образом, реакция автомата на каждое значение вход­ного сигнала заканчивается за один такт, длительность которого определяется интервалом между соседними синхронизирующими сигналами. Асинхронный F-автомат считывает входной сигнал непрерывно, и поэтому, реагируя на достаточно длинный входной сигнал постоянной величины х, он может, как следует из (3.1) — (3.5), несколько раз изменять состояние, выдавая соответству­ющее число выходных сигналов, пока не перейдет в устойчивое, которое уже не может быть изменено данным входным сигналом.

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

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

Описание работы F-автомата Мили таблицами переходов φ и выходов ψ иллюстрируется табл. 3.1, а описание F-автомата Мура - таблицей переходов (табл. 3.2).

 

Таблица 3.1

xj	zk
z0	z1	…	zk

Переходы

x1	φ(z0,x1)	φ(z1,x1)	…	φ(zk,x1)
x2	φ(z0,x2)	φ(z1,x2)	…	…
…	…	…	…	φ(zk,x2)
x1	φ(z0,x1)	φ(z1,x1)	…	φ(zk,x1)

Выходы

x1	ψ(z0,x1)	ψ (z1,x1)	…	ψ (zk,x1)
x2	ψ (z0,x2)	ψ (z1,x2)	…	ψ (zk,x2)
…	…	…	…	…
x1	ψ (z0,x1)	ψ (z1,x1)	…	ψ (zk,x1)

 

Таблица 3.2

xi	ψ(zk)
ψ(z0)	ψ(z1)	…	ψ(zk)
z0	z1	…	zk
x1	φ(z0,x1)	φ(z1,x1)	…	φ(zk,x1)
x1	φ(z0,x2)	φ(z1,x2)	…	…
…	…	…	…	φ(zk,x2)
x1	φ(z0,x1)	φ(z1,x1)	…	φ(zk,x1)

 

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

 

 

Таблица 3.3

xi	zk
z0	z1	z2

Переходы

x1	z2	z0	z0
x2	z0	z2	z1

Выходы

x1	y1	y1	y2
x2	y1	y2	y1

 

Таблица 3.4

xi	y
y1	y1	y3	y2	y3
z0	z1	z2	z3	z4
x1	z1	z4	z4	z2	z2
x2	z3	z1	z1	z0	z0

 

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

На рис. 3.1, а, б приведены заданные ранее таблицами F-автома­ты Мили F1 и Мура F2 соответственно.

 

б)

a)

y1

x1

x2

x1

y1

x2

 

Рис. 3.1 Графы автоматов Мили(а) и Мура(б)

 

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

состояние z_j и выходному сигналу y_s, вы­даваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид

.

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

Для F-автомата Мура элемент с_ij равен множеству входных сигналов на переходе (z_i zj), а выход описывается вектором выходов

,

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

 

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