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

рассмотрим на примере использования в качестве математического аппарата те­ории автоматов. Теория автоматов — это раздел теоретической кибернетики, в котором изучаются математические модели — авто­маты.

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

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

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

§ конечным множеством X входных сиг­налов (входным алфавитом);

§ конечным множеством Y выходных сигналов (выходным алфавитом);

§ конечным множеством Z внут­ренних состояний (внутренним алфавитом или алфавитом состоя­ний);

§ начальным состоянием z₀, z₀ Є Z;

§ функцией переходов φ(z, х);

§ функцией выходов ψ (z, х).

Автомат, задаваемый F-схемой: F=<Z, X, Y, φ, ψ, z₀>,- функционирует в дискретном автоматном време­ни, моментами которого являются такты, т. е, примыкающие друг к другу равные интервалы времени, каждому из которых соответ­ствуют постоянные значения входного и выходного сигналов и вну­тренние состояния.

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

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

Автомат 1ого рода называется также автоматом МИЛИ.

2ого рода называется автоматом МУРа.

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

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

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

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

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

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

При решении задач моделирования систем часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица С=||с_y||, строки которой соответствуют исходным состояниям, а столбцы — состояниям перехода.

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

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

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