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

Детерминированные системы с дискретными состояниями, функционирующие в дискретном времени называют конечными автоматами или F-системами (Finite — конечный).

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

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами:

• — конечным множеством X входных сигналов (входным алфавитом);
• — конечным множеством Y выходных сигналов (выходным алфавитом);
• — конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний);
• — начальным состоянием z₀, z_oZ;
• — функцией переходов ц (z, х);
• — функцией выходов ш (z, x).

Автомат, задаваемый F-схемой: F=(Z, X, Y, ц, ш, zo), — функционирует в дискретном автоматном времени, моментами которого являются такты, т. е. примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t-му такту при t=0, 1, 2, …, через z (t), x (t), y (t). При этом по условию, z (0)=zo, a z (i) Z, x (t) X, y (t) Y.

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

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

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

z (t+1) = ц[z (t), x (t)], t = 0,1,2,… (3.1).

y (t+1) = ш[z (t), x (t)], t = 0,1,2,… (3.2).

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

z (t+1) = ц[z (t), x (t)], t = 0, 1,2,… (3.3).

y (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.2), работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x (t) определенный выходной сигнал y (t), т. е. реализует логическую функцию вида.

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

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

По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные.

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

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