Конечные автоматы - раздел Образование, АНАЛИТИЧЕСКИЕ И ИМИТАЦИОННЫЕ МОДЕЛИ Для Моделирования Динамических Систем, Функционирующих В Дискретном Времени, ...
Для моделирования динамических систем, функционирующих в дискретном времени, применяется аппарат конечных автоматов [7]. Теория конечных автоматов и их модели используются при синтезе и анализе вычислительных устройств, дискретных устройств автоматики. Конечный автомат функционирует в дискретные моменты времени t, причем в каждый момент tiавтомат находится в одном из возможных состояний z(ti), принадлежащем множеству состояний автомата Z. Математические модели в виде конечного автомата получили название F-схем от английского finite automata – конечный автомат.
В каждый момент ti(i=1,2,...) на вход конечного автомата поступает входной параметр - одна из букв х(ti) входного алфавита Х, а на выходе существует выходной параметрy(t) - буква выходного алфавита Y.
Автомат формально определен набором
A=<Х,Z,Y,z0,j,y>,
где Х={х1,х2,...,хm} -множество входных параметров; Z={z1,z2,...,zn} - множество состояний; Y={y1,y2,...,yr} - множество выходных параметров. Элементы множества Х, Z, Y называют входным, внутренним и выходным алфавитом. При поступлении параметра х состояние конечного автомата изменяется в соответствии с одношаговой функцией переходов, например:
z(t)=j[z(t-1),х(t)] илиz(t)=j[z(t),х(t)],
а выходной параметр y(t) определяется функцией выходов, которая может иметь следующие виды задания:
Функции переходов и выходов могут быть заданы теоретико-множественным способом, табличным способом и в виде графов. Рассмотрим пример задания конечного автомата.
Функция переходов для данного автомата задана в виде табл. 2.1, а функция выходов вида y(t)=y[z(t),х(t)] – в виде табл. 2.2.
Таблица 2.1
Функция переходов
Х
Z
z1
Z2
z3
z4
х1
z1
Z2
z3
z4
х2
z2
Z3
z4
z1
х3
z4
Z1
z2
z3
Таблица 2.2
Функция выходов
Х
Z
z1
z2
z3
z4
х1
y1
y4
y3
y2
х2
y2
y1
y4
y3
х3
y3
y2
y1
y4
При задании функции переходов на пересечении i–й строки и j–го столбца указывается состояние zk, в которое переходит автомат при подаче входного параметра хi в такте времени t, при условии, что в такте времени t-1 автомат находился в состоянии zj.
На рис. 2.4 приведено графическое задание функции переходов рассматриваемого автомата.
Рис. 2.4
Автомат в процессе своей работы реализует отображение множества слов (последовательность параметров) входного алфавита Х на множество слов выходного алфавита Y. Если на вход конечного автомата, установленного в начальное состояние z0, подать последовательность букв входного алфавита х(t0), х(t1), х(t2),…, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(t0), y(t1), y(t2),…
В зависимости от способа заданий функций переходов и выходов, автоматы подразделяются на автоматы первого и второго рода. Для автомата первого рода, называемого автоматом Мили, функция переходов имеет вид z(t)=j[z(t),х(t)], а функция выходов - y(t)=y[z(t),х(t)].
Для автомата второго рода функция переходов имеет вид: z(t)=j[z(t),х(t)], а функция выходов - y(t)=y[z(t-1),х(t)].
Автомат второго рода, функция выходов которого определяется его состоянием - y(t)=y[z(t)], называется автоматом Мура.
По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти обладают лишь одним состоянием. Автоматы без памяти называют комбинационными или логическими схемами. Функция выходов такого автомата - y(t)=y[х(t)].
Если множества Х и Y состоят из двух параметров, то функции переходов и выходов называются булевыми функциями.
Рассмотрим примеры моделирования систем в виде конечных автоматов.
Пример 1. Автомат для продажи билетов в автобусах принимает монеты достоинством в 1,2 и 5 рублей и выдает билеты стоимостью 5 рублей. Рассмотрим конечный автомат Мили с множеством состояний Z=(0,1,2,3), входным алфавитом Х=(1,2,5) и выходным алфавитом Y=(0,1), где 0 соответствует ситуации «билет не выдается», а 1 – ситуации «билет выдается».
Функция переходов j(t) определяется соотношением
Z(t)=(z(t-1)+х(t))mod5,
а функция выходов y(t) – соотношением
Пример 2.Хранилище склада материально-техническогоснабжения состоит из стеллажей, предназначенных для хранения материальных ценностей.
Изделия i-й номенклатуры хранятся в i-м стеллаже (i=1,2,…,n). Содержание стеллажей изменяется в моменты времени поступления на склад новых изделий потребителям. Такое хранилище можно представить в виде конечного автомата Мура. В качестве состояний выберем n-мерный вектор Z=(Z1,Z2,…,Zn), где Zi - число изделий на i-м стеллаже.
Выходной сигнал – (n+1) – мерный вектор Х=(Х1,Х2,…, Хn,m), где Хi - число изделий i-й номенклатуры, поступивший на склад или выданный потребителю. При поступлении изделий на склад m=1, а при выдаче изделий потребителю m= -1. Выходной сигнал представляет собой n–мерный вектор Y=(Y1,Y2,…,Yn), для которого Yi(t)=Zi(t) – информация о состоянии стеллажей.
Функция переходов определена соотношением
Zi(t)=Zi(t-1)+mх(t),
а функция выходов определена соотношением
Yi(t)=Zi(t).
На рис. 2.5 приведен алгоритм программы моделирования конечного автомата, функция выходов которого имеет задание z(t)=j[z(t-1),х(t)], а функция переходов - y(t)=y[z(t),х(t)]. Функция переходов задается в подпрограмме WWOD в виде массива FР(i,j), значения которого определены индексом k состояния zk, в которое переходит автомат при подаче входного параметра хi в такте времени t, при условии, что в такте времени t-1 автомат находился в состоянии zj.
Рис. 2.5
Функция выходов задается в подпрограмме WWOD в виде массива FW(i,k), значения которого определены индексом w выходного параметра (буквы) yw, который будет на выходе автомат при подаче входного параметра хi в такте времени t, при условии, что в этом такте времени t автомат находится в состоянии zk. В подпрограмме WWOD происходит инициализация автомата, т.е. определение z0=zk. В блоке 3 алгоритма происходит изменение индекса состояния с учетом задержки на один такт.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ... Технологический институт... Федерального государственного образовательного учреждения высшего профессионального образования...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Конечные автоматы
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
СТОХАСТИЧЕСКИЕ МОДЕЛИ
ОБЪЕКТОВ………………………………………..……. 46
3.1. Математические модели случайных процессов..… 46
3.2. Классификация моделей случайных процессов..… 53
3.3. Модели мар
МОДЕЛИ СИСТЕМ
МАССОВОГО ОБСЛУЖИВАНИЯ……..…………... 147
7.1. Общие сведения…..………………………………..... 147
7.2. Модель входного потока заявок
и времени обслуживания…..…………………….……
УНИФИЦИРОВАННЫЙ
ЯЗЫК МОДЕЛИРОВАНИЯ UML…………..………. 229
9.1. Основные компоненты…………..…………………. 229
9.2. Понятия и компоненты…………..…………………. 231
9.3. Диаграммы вариантов испо
Понятие модели
1.1.1. Системный подход к моделированию. При проектировании автоматизированных систем управления, разработке прикладных программных продуктов важно правильно постав
Концепции определения моделей
Под динамической системой понимается объект, находящийся в каждый момент времени tÎT в одном из возможных состояний
Инерционные модели
Динамические системы с последействием (с предысторией) могут быть формализованы с применением дифференциальных уравнений с запаздывающим аргументом.
2.3.1. Дифференциальные уравнен
Модели на основе передаточных функций
Рассмотрим однооткликовую импульсную систему с дискретными сигналами на ее входе и выходе, модель которой может быть выражена с помощью импульсной характеристики (весовой функции) в виде уравнения
СТОХАСТИЧЕСКИЕ МОДЕЛИ ОБЪЕКТОВ
3.1. Математические модели случайных процессов
При проведении научных исследований в производстве и в быту часто встречаются события, которые многократно появляются при одн
Понятие статистического моделирования
При определении методов статистического моделирования применяют название «метод Монте-Карло». Определение, которое характеризует этот метод достаточно точно и полно, не существует. Известно, что эт
Датчики случайных чисел
Для имитации случайных событий необходим некоторый эталон, т.е. то, с чем можно что-то сравнить. Известно, что наука существует там, где есть измерения. Отсутствие измерений приводит к схоластике,
Проверочные тесты
Программная реализация датчика псевдослучайных, квазиравномерно распределенных чисел может быть получена любым программистом на основе разработанного им алгоритма с применением либо аналитических м
Имитация случайных событий
Пусть события S1, S2,..., Smобразуют полную группу несовместимых событий, каждое из которых может произойти с вероятностью Рi, причем
Имитация непрерывных случайных величин
Если событие Х принимает значения в некоторой области непрерывных величин, то для аналитического моделирования непрерывных событий применяют функцию распределения вероятностей
Имитация марковского процесса
4.6.1. Моделирование дискретной цепи Маркова. Рассмотрим дискретную цепь Маркова или марковский процесс с дискретным временем перехода из одного состояния в другое. Математическая
Выбор числа опытов
При разработке имитационных моделей для исследования случайных объектов существует задача выбора числа опытов (объема выборки). Это непростая задача, т.к. во-первых, необходимо обосновать достоверн
Формулы и алгоритмы для оценки результатов моделирования
При реализации моделирующего алгоритма на ЭВМ вырабатывается информация о состоянии моделируемых систем, которая представляет собой исходный материал для определения приближенных ис
Аналитическое определение вероятностных автоматов
6.1.1. Формальное задание и классификация. Вероятностные автоматы (ВА) относятся к дискретно-стохастическому классу моделей. Данный тип моделей служит инструментом изучения динамич
Имитационное моделирование вероятностных автоматов
Для имитации процесса функционирования ВА необходимо задать:
- такты моделирования T, а также цикл по тактам моделирования от нуля до заданного числа такто
Модель Эрланга
При моделировании СМО исследуется изменение в системе за сколь угодно малый отрезок времени. Составляются уравнения в частных приращениях, от которых затем осуществляется переход к дифференциальным
Имитационное моделирование одноканальной СМО
Алгоритмизация может осуществляться с применением способа Dt-моделирования, который позволяет определить состояния СМО через интервал времени Dt.
Имитационные модели многофазных СМО
Пусть СМО имеет структуру, показанную на рис. 7.18, т.е. обслуживание состоит из двух фаз. Входной поток заявок задан функцией распределения вероятностей длин интервалов между заявками A(t)
Имитационные модели многоканальных СМО
7.8.1. Модели систем с общей очередью.Рассмотрим задачу построения имитационной модели трехканальной СМО с общей очередью. Понятие общей очереди предусматривает, чт
Моделиpующие алгоpитмы
Для моделиpования любого объекта, заданного пpи помощи математичеcкой модели, а также в виде последовательности процедур, имитирующих отдельные элементарные процессы, необxодимо поc
Основные компоненты
После многх попыток создания унифицированных языков для решения задач моделирования был разработан и опробован объектно-ориентированный подход. Первый язык Simula-67, основанный на
Понятия и компоненты
Сущности представляются парами «тип, экземпляр». Таких пар несколько: «класс, объект», «ассоциация, связь», «параметр, значение», «операция, вызов процедуры». Для изображения элемен
Array, Real, Vektor, Matrix.
Описание типа зависит от того, какой язык программирования используется разработчиками. Атрибуг изображается в виде текстовой строки, отражающей различные его свойства:
<признак
Масса машины
…
У каждой секции прямоугольника класса может быть имя. Так как секция «имя класса» обязательна, то ее имя не указывается, как показано на рис. 9.6.
Связи между объектами
Аналогично ключевому понятию модели классов - понятию ассоциации, - для объектов существует понятие связи (link). Связь есть экземпляр ассоциации, установленной для объектов данных
Диаграммы взаимодействия
Взаимодействия между объектами в системе представляются диаграммами взаимодействия (interaction diagrams). Диаграммы взаимодействия подразделяются на два основных типа диаграмм: диаграммы последова
Диаграммы состояний
Диаграммы состояний (state diagram) определяют состояния, в которых может находиться конкретный объект, а также процесс смены состояний объекта в результате влияния некоторых событи
Диаграммы деятельностей
Диаграммы деятельностей (aktivity diagrams) предназначены для того, чтобы отразить переходы в рамках выполнения определенной задачи, вызванные внутренними процессами. Используются для моделирования
Определение объекта
Объектно-ориентированный подход в последнее время стал прочно ассоциироваться с программированием. Объектно-ориентированный подход развивался почти исключительно программистами. Ито
Наследование
Наследование в ООМ понимается примерно так же, как и в ООП. Если объявляете класс с2 прямым потомком класса с1, то класс с2 наслед
Полиморфизм
Полиморфизмом в ООП называется возможность использования вместо объектов одного декларированного класса объекты другого класса, называемого замещающим, совместимого с первым. Аналог
Equation
Z= X/K;
endCMulGiv;
Новый класс CMulGiv наследует от своего суперкласса CGain вход, выход, параметр и одно уравнение, а также добавляет один выхо
Equation
Y = if X>Xmax then UpperLimit
else if X<Xmin then LowerLimit
else K*X;
Equation
connect(Gem.Y,Amp.X);
connect(Gem.Y,Y);
endCSineSource;
Далее нужно создать специальный класс CLimitedSineSource на основе СSineSource, переопределив пар
Типы данных и пакеты
Для моделирования непрерывных систем необходим минимальный набор типов данных: скалярный вещественный тип, типы «вектор» и «матрица», а также целые числа для вычисления индексов век
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Советов Б.Я., Яковлев С.А. «Моделирование систем». – М.: Высш. школа, 1985 – 271 с.
2. Бусленко Н.П. Моделирование сложных систем. – М.: Наука,1978. – 400 с.
3. Финаев В.И. Мод
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов