Дискретно – детерминированные модели (F-схемы)

ДДМ являются предметом рассмотрения теории автоматов (ТА). ТА - раздел теоретической кибернетики, изучающей устройства, перерабатывающие дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени.

Конечный автомат имеет множество внутренних состояний и входных сигналов, являющихся конечными множествами. Автомат задаётся F- схемой: F=<z,x,y,j,y,z₀>, (1)

где z,x,y - соответственно конечные множества входных, выходных сигналов (алфавитов) и конечное множество внутренних состояний (алфавита). z₀ÎZ - начальное состояние; j(z,x) - функция переходов; y(z,x) - функция выхода. Автомат функционирует в дискретном автоматном времени, моментами которого являются такты, т.е. примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного, выходного сигнала и внутреннего состояния. Абстрактный автомат имеет один входной и один выходной каналы.

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

Существуют F- автомат 1-ого рода (Миля), функционирующий по схеме:

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

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

F- автомат 2-ого рода:

z(t+1)= j[z(t),z(t)], t=0,1,2… (3)

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

Автомат 2-ого рода, для которого y(t)=y[z(t)], t=0,1,2,… (5)

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

Т.о. уравнения 1-5 полностью задающие F- автомат, являются частным случаем уравнения

(6)

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

когда система S - денорминированная и на её вход поступает дискретный сигнал x.

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

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

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

По характеру отсчёта времени (дискретному) F- автоматы делятся на синхронные и асинхронные. В синхронных автоматах моменты времени, в которые автомат "считывает" входные сигналы, определяются принудительно синхронизирующими сигналами. Реакция автомата на каждое значение входного сигнала заканчивается за один такт синхронизации. Асинхронный F- автомат считывает входной сигнал непрерывно и поэтому, реагируя на достаточно длинный водной сигнал постоянной величины x, он может, как это следует из 1-5, несколько раз изменить своё состояние, выдавая соответствующее число выходных сигналов, пока не перейдёт в устойчивое.

Для задания F- автомата необходимо описать все элементы множества F=<z,x,y,j,y,z₀>, т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов. Для задания работы F- автоматов наиболее часто используются табличный, графический и матричный способ.

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

Описание работы F- автомата Мили таблицами переходов j и выходов y иллюстрируется таблицей (1), а описание F- автомата Мура - таблицей переходов (2).

Таблица 1

Таблица 2

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

Таблица 3

Таблица 4

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

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

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

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

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

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

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

;

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

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

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

Пример. Рассмотрим асинхронный F- автомат Мура, который описан в табл. 5 и приведён на рис. 2.

Таблица 5

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

Если в таблице переходов асинхронного автомата некоторое состояние z_k стоит на пересечении строки x_S и столбца z_S(S¹k), то это состояние z_k обязательно должно встретиться в этой же строке в столбце z_k.

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