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

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

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

Понятие «состояние» автоматаозначает, что выходной сигнал автомата зависит не только от входных сигналов в данный момент времени, но и учитывает входные сигналы, поступающие ранее. Это позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.

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

Существует два способа введения автоматного времени по которому автоматы делятся на синхронные и асинхронные.

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

В асинхронном автомате моменты перехода автомата из одного состояния в другое заранее не определены и зависят от конкретных событий. В таких автоматах интервал дискретности является переменным.

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

Абстрактно конечный автомат можно представить как математическую схему (F – схему), которая характеризуется шестью видами переменных и функций:

1) конечное множество x(t) входных сигналов (входной алфавит);

2) конечное множество y(t) выходных сигналов (выходной алфавит);

3) конечное множество z(t) внутренних состояний (алфавит состояний);

4) начальное состояние автомата z₀ , ;

5) функция переходов автомата из одного состояния в другое;

6) функция выходов автомата.

Абстрактный конечный автоматимеет один вход и один выход. В каждый дискретный момент времени t=0,1,2,... F– автомат находится в определенном состоянии z(t) из множества Z – состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии z(0)=z₀ . В момент t , будучи в состоянии z(t), автомат способен воспринять на входном канале сигнал и выдать на выходном канале сигнал , переходя в состояние

, где .

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

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

В зависимости от способа определения выходного сигнала синхронные абстрактные конечные автоматы подразделяются на два типа:

- F – автомат первого рода, также называется автомат Мили:

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

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

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

Чтобы задать конечный F – автомат, необходимо описать все элементы множества

.

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

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

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

Таблица 3.1. Автомат Мили

Таблица 3.2. Автомат Мура.

Пример задания автоматов Мили F1 и Мура F2 приведен в таблицах 3.3 и 3.4.

Таблица 3.3. Пример автомата Мили

Таблица 3.4. Пример автомата Мура

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

На рис. 3.4 в виде графов приведены автоматы Мили и Мура, заданные таблицами 3.3 и 3.4.

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

При решении задач моделирования систем более удобной формой является матричное задание конечного автомата.

При этом матрица соединений автомата есть квадратная матрица

,

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

В случае автомата Мили элемент соответствует входному сигналу , вызывающему переход из состояния в состояние и выходному сигналу , выдаваемому при этом переходе.

Рис. 3.5. Пример автомата Мили F1.

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

.

Для рассмотренного примера таблицы автомат Мура имеют вид:

.

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