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

(F -СХЕМЫ)

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

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующу­юся шестью элементами: конечным множеством X входных сиг­налов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внут­ренних состояний (внутренним алфавитом или алфавитом состоя­ний); начальным состоянием , ;функцией переходов ; функцией выходов . Автомат, задаваемый F-схемой: ,— функционирует в дискретном автоматном време­ни, моментами которого являются такты, т. е. примыкающие друг к другу равные интервалы времени, каждому из которых соответ­ствуют постоянные значения входного и выходного сигналов и вну­тренние состояния. Обозначим состояние, а также входной и выход­ной сигналы, соответствующие t -му такту при через , , . При этом, по условию, , а , , .

Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент дискретного времени F-автомат находится в определенном состоянии из множества Z состояний автомата, причем в начальный момент времени он всегда находится в начальном состоянии . В момент , будучи в состоянии , автомат способен воспринять на входном канале сигнал и выдать на выходном канале сигнал , переходя в состояние , , . Абстрактный конечный автомат реализует некото­рое отображение множества слов входного алфавита Х на множест­во слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние , по­давать в некоторой последовательности буквы входного алфавита , , , …, т. е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита , , , …, образуя выходное слово.

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

(2.13)

(2.14)

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

(2.15)

(2.16)

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

(2.17)

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

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

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

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

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

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

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

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

Таблица 2.1

		…
Переходы
…	…	…	… … … …	…
Выходы
…	…	…	… … … …	…

Таблица 2.2

		…
		…
…	…	…	… … … …	…

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

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

Таблица 2.3

Переходы
Выходы

Таблица 2.4

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

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

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

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

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

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

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

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

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

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

Таблица 2.5

Пример 2.3. Рассмотрим асинхронный F-автомат Мура, который описан табл. 2.5 и приведен на рис. 2.4. Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние стоят на пересечении строки в столбца , то это состояние обязательно должно встретиться в этой же строке в столбце . В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине должна быть петля, отмеченная символами тех же входных сигналов. Анализ табл. 2.3 и 2.4 или рис 2.3, б и 2.4 показывает, что представленные там F-автоматы F1 и F2 являются синхронными.

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

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: