|
ДИСКРЕТНО-ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ(F -СХЕМЫ)
Особенности дискретно-детерминированного подхода на этапе формализации процесса функционирования систем рассмотрим на примере использования в качестве математического аппарата теории автоматов. Теория автоматов — это раздел теоретической кибернетики, в котором изучаются математические модели — автоматы. На основе этой теории система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. Понятие «автомат» варьируется в зависимости от характера конкретно изучаемых систем, от принятого уровня абстракции и" целесообразной степени общности. Основные соотношения. Автомат можно представить как некоторое устройство (черный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния. Конечным автоматом называется автомат, у которого множество внутренних состояний и входных сигналов (а, следовательно, и множество выходных сигналов) являются конечными множествами. Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством X входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t -м такте на вход автомата, находящегося в состоянии
для F -автомата второго рода
Автомат второго рода, для которого
т. е. функция выходов не зависит от входной переменной Таким образом, уравнения (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-автомата Мили таблицами переходов
Таблица 2.1
Таблица 2.2
Примеры табличного способа задания F-автомата Мили F1 с тремя состояниями, двумя входными и двумя выходными сигналами приведены в табл. 2.3, а для F-автомата Мура F2 — в табл. 2.4. При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал
Таблица 2.3
Таблица 2.4
На рис. 2.3, а, б приведены заданные ранее таблицами F-автоматы Мили F1 и Мура F2 соответственно. При решении задач моделирования систем часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица Если переход из состояния Для F-автомата Мура элемент i -я компонента которого — выходной сигнал, отмечающий состояние Пример 2.2. Для рассмотренного выше F-автомата Мура F2 запишем матрицу соединений и вектор выходов:
Для детерминированных автоматов выполняется условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания F-автомата это означает, что в графе автомата из любой вершины не могут выходить два ребра и более, отмеченные одним и тем же входным сигналом. Аналогично этому в матрице соединений автомата С в каждой строке любой входной сигнал не должен встречаться более одного раза. Рассмотрим вид таблицы переходов и графа асинхронного конечного автомата. Для F-автомата состояние Необходимо отметить, что вообще на практике автоматы всегда являются асинхронными, а устойчивость их состоянии обеспечивается тем или иным способом, например введением сигналов синхронизации. Однако на уровне абстрактной теории, когда конечный автомат выступает в виде математической схемы для формализации конкретных объектов без учета ряда второстепенных особенностей, часто удобно оказывается оперировать с синхронными конечными автоматами. Таблица 2.5
Пример 2.3. Рассмотрим асинхронный F-автомат Мура, который описан табл. 2.5 и приведен на рис. 2.4. Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние
Таким образом, понятие F-автомата в дискретно-детерминированном подходе к исследованию на моделях свойств объектов является математической абстракцией, удобной для описания широкого класса процессов функционирования реальных объектов в автоматизированных системах обработки информации и управления. В качестве таких объектов в первую очередь следует назвать элементы и узлы ЭВМ, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией и т. д. Для всех перечисленных объектов характерно наличие дискретных состояний и дискретный характер работы во времени, т. е. их описание с помощью F-схем является эффективным. Но широта их применения не означает универсальности этих математических схем. Например, этот подход непригоден для описания процессов принятия решении, процессов в динамических системах с наличием переходных процессов и стохастических элементов.
![]() ![]() Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... ![]() Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... ![]() ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... ![]() Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|