Простейший пример создания имитационной модели по текстовому описанию системы

Рассмотрим в упрощенном варианте функционирование микроволновой печи и проведем объектное проектирование с последующей реализацией и моделированием ее работы.

Перечислим правила функционирования микроволновой печи:

• Имеется единственная кнопка управления, доступная пользователю, которая включает печь и добавляет время приготовления пищи.

• Печь также управляется посредством открытия и закрытия дверцы.

Кроме того, существуют элементы, которые служат индикаторами состояния печи:

1. таймер, который указывает время, оставшееся до конца приготовления пищи на момент наблюдения;

2. элемент питания, который может находиться в двух состояниях: включен и выключен;

3. электрическая лампочка, возможные состояния которой также включена и выключена;

4. Индикатором состояния также является дверца, которая может быть открыта или закрыта;

Выше перечисленные индикаторы не являются независимыми, а работают следующим образом:

Если дверца печи открыта, и лампа не горит, то предполагается, что печь не подключена к источнику питания и такое состояние мы не рассматриваем.

a). Если дверь печи закрыта и лампа не горит, то питание выключено. При этом таймер показывает нулевое время. Это нормальная конфигурация, если пищу поместили в печь, но не нажали кнопку или когда пища приготовилась, т.е. таймер уменьшился до нуля и питание автоматически выключилось.

b). Когда дверь печи закрыта и работает питание, также горит и лампа. При этом таймер показывает ненулевое значение. Это состояние, в котором идет приготовление пищи.

c). Когда дверь открыта, питание всегда выключено, а лампа горит. Это состояние, в котором пища помещается и извлекается из микроволновой печи. При этом таймер показывает нулевое значение.

Таким образом, мы выделяем три состояния микроволновой печи. При этом, из состояния «a» можно перейти в состояние «b» нажав кнопку управления. При этом таймер изменяет нулевое значение на 1мин. Если мы откроем дверь печки, которая находится в состоянии «a» или «b», мы переходим в состояние «c». При закрытии двери мы переходим в состояние «a». Если нажать кнопку управления при включенном питании, то добавится дополнительная минута.

Теперь спроектируем данную систему. Основным инструментом построения математической модели данной системы служит понятие конечного автомата.

Детерминированный конечный автомат-распознаватель (ДКА) – это пятерка символов (∑, Q, φ, q₀ , F), такая, что ∑, Q, F – произвольные непустые конечные множества. Множество ∑ ={a₁, a₂, …, a_m} называется входным алфавитом, а элементы a_i – символы алфавита. Q – конечное множество состояний автомата Q={q₁, q₂, …, q_n}, а q₀Q – начальное (стартовое) состояние автомата. Множество F Q называется множеством конечных состояний автомата. Функция φ: ∑×Q→ Q называется функцией переходов. Если для (q₁, q₂ ) Q и a∑ имеем φ(a, q₁)= q₂ , то мы говорим, что автомат переходит из состояния q₁ в состояние q₂ под действием символа a. С конечным автоматом ассоциируется воображаемое устройство, которое работает следующим образом. Оно может находиться в состоянии из множества Q, воспринимать сигналы из множества ∑ и под их действием переходить в другое состояние из Q. При этом может быть q₁=q₂.

В дальнейшем нам понадобятся следующие определения. Под словом алфавита ∑ мы понимаем произвольную конечную последовательность символов из ∑ . Каждое слово имеет длину, которая является некоторым натуральным числом и равна количеству символов в этом слове. Множество всех слов алфавита мы обозначим через ∑^*. В ∑^* имеется слово нулевой длины, которое обозначается через e и называется пустым словом. На множестве слов ∑^* определена операция конкатенации. Конкатенация слов w и v это такое слово, в котором сначала идут все символы слова w, а прямо следом ними все символы слова v. Конкатенация слов обозначается через wv. Операция конкатенации некоммутативна, но ассоциативна, т.е. u(vw)=(uv)w. Пустое слово играет роль единицы при умножении, т.е. we=ew=w. Мы говорим, что слово w является началом слова v, если существует слово u, такое что v=wu. При этом мы пишем wv. Под языком L алфавита ∑ мы понимаем произвольное подмножество множества ∑^*, т.е. L∑^*.

Определим расширенную функцию переходов Φ: ∑^*×Q→ Q автомата (∑, Q, φ, q_{0 ,} F), которая сопоставляет каждой паре, состоящей из слова ξ ∑^* алфавита ∑ и состояния qQ , некоторое состояние автомата. Причем, значение Φ(ξ,q) определяется индукцией по длине слова ξ согласно следующей схеме:

1. qQ Φ(e,q)=q;

2. qQ , ξ ∑^*, a∑ Φ(ξa,q)= φ(a, Φ(ξ,q))

Если для (q₁, q₂) Q и ξ ∑^* Φ(ξ,q₁)=q₂ , то мы говорим, что автомат переходит из состояния q₁ в состояние q₂ под действием слова ξ. Смысл функции Φ заключается в следующем: значение Φ(ξ,q) равно состоянию, в которое перейдет автомат, если он, находясь в состоянии q, начнет последовательно читать символы слова ξ и осуществлять под действием этих символов переходы между состояниями согласно функции переходов φ.

Слово ξ ∑^* алфавита ∑ распознается автоматом (∑, Q, φ, q_{0 ,} F), если Φ(ξ,q₀) F, т.е. если автомат под действием слова ξ переходит из начального состояния в одно из конечных состояний. Множество всех слов, распознаваемых автоматом называется языком, распознаваемым автоматом: L={ ξ ∑^* , Φ(ξ,q₀) F }.

Таким образом, автоматы — это устройства для распознавания языков. Автомат можно рассматривать как представление алгоритма для вычисления функции, действующей из конструктивного пространства ∑^* в конструктивное пространство возможных ответов {да, нет}. Другими словами, автомат — это алгоритм, который, получив на входе слово ξ, дает ответ на вопрос: «Верно ли, что ξ L ?»

Детерминированный конечный автомат-преобразователь.

Для того, чтобы наделить модель абстрактного конечного автомата способностью не только давать ответ типа {да, нет}, но и выполнять какие-либо преобразования, в модель добавляют конечный алфавит выходных символов Z и функцию выхода ψ. Если функция выхода имеет вид ψ: ∑×Q→Z, то такой автомат называется автоматом Мили, а если ψ: Q→Z, то вычислитель называется автоматом Мура. Таким образом, рассматривается набор символов (∑, Q, Z, φ, q₀ , ψ). Данный вычислитель определяет отображение Ψ: ∑^*→ Z^* (преобразование, выполняемое автоматом или автоматное преобразование) следующим образом:

1. Ψ(e)=e;

2. ξ ∑^*, a∑ Ψ(ξa)= Ψ(ξ) ψ(a, Φ(ξ,q₀)).

Автоматные отображения – это отображения «без предсказания»: обрабатывая цепочку слева направо, они «не заглядывают вперед». Например, отображение, которое сопоставляет слову само слово, записанное в обратном порядке, не является автоматным.

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

• Событий, на которые реагирует программа;

• Состояний, в которых программа пребывает между событиями;

• Переходов между состояниями при реагировании на события;

• Действий, выполняемых в процессе переходов;

• Переменных, которые содержат значения, необходимые для выполнения действий между событиями.

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

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

Существует три распространенных представления конечных автоматов:

1. Двумерная таблица;

2. Диаграмма Мура;

3. Система булевых функций.

Методичная разработка поведения

Реализуем теперь систему микроволновая печь как конечный автомат при помощи вышеупомянутых механизмов. Основные ингредиенты для конечного автомата - это события, на которые он реагирует, и состояния, в которых он ожидает между событиями. Проект должен предусматривать все возможные события для всех возможных состояний:

• Может ли событие наступить в этом состоянии;

• Какое действие следует выполнить для обработки событий;

• В какое состояние будет выполнен переход после наступления события;

• Какие переменные следует запомнить между событиями.

Начнем проектирование с построения диаграммы Мура, на которой состояния показаны в виде прямоугольников, а переходы в виде стрелок. Это стандарт языка UML. Мы создадим некоторые состояния, в которых конечный автомат будет ожидать между событиями. В нашем случае это состояние с открытой дверью, т.е. состояние «c». Также состояние, в котором готовится пища (состояние «b») и состояние «a» с закрытой дверью и выключенном питанием. Событиями, благодаря которым происходят переходы между данными состояниями, являются: нажатие кнопки, открытие и закрытие двери, отсчет времени таймера. Давайте назовем исходное состояние «c» с открытой дверью FoodInOut. Это такое состояние, в котором печь будет ожидать события «закрыть дверь» Shutting the door. После наступления данного события печь переходит в состояние «a», в котором дверь закрыта, а питание выключено. Назовем это состояние Stop. В данном состоянии печь будет ожидать, либо открытия двери (событие Opening the door) чтобы вернуться в исходное состояние FoodInOut, либо нажатия кнопки (событие Press the button) для того, чтобы перейти в состояние «b», в котором готовится пища. Назовем это состояние Cooking. В состоянии Cooking возможно наступление следующих событий. Открытие двери Opening the door, при этом попадаем в состояние FoodInOut; Событие Press the button лишь добавляет время приготовления, но не меняет состояния Cooking; Событие Timer также не меняет состояния Cooking, если счетчик секунд показывает ненулевое время. Если же счетчик времени при наступлении очередного события Timer принимает значение ноль, то осуществляется переход из состояния Cooking в состояние Stop.

Все переходы изображены на диаграмме. Таким образом, мы определили каркас нашей модели. Однако, при наступлении какого-либо события, выполняются не только переходы между состояниями, но и выполняются определенные действия. Поэтому на втором этапе проектирования мы определим действия для каждого события.

1. При наступлении события Shutting the door гаснет лампа.

2. Когда печь находится в состоянии Stop, событие Opening the door сопровождается зажиганием лампы.

3. Если печь находится в состоянии Cooking, то событие Opening the door сопровождается обнулением показаний таймера и выключением питания.

4. Если печь находится в состоянии Stop и при этом наступает событие Press the button, то зажигается лампа, включается питание и запускается счетчик, при этом показания последнего увеличиваются с нуля до 60 с.

5. Если печь находится в состоянии Cooking и при этом наступает событие Press the button, то к показаниям таймера добавляется 10 с.

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

Добавим эти действия к нашей диаграмме:

Перевод диаграммы Мура в двумерную таблицу состояний

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

Чтобы перевести граф состояний в таблицу состояний, в качестве заголовков строк выберем названия событий, а в качестве заголовков столбцов - названия состояний. Порядок названий может быть произвольным;

Первоначальная таблица состояний, соответствующая диаграмме Мура

События\Состояния	FoodInOut	Stop	Cooking
Shutting the door	Lamp switch off; Stop
Opening the door		Lamp switch on; FoodInOut	Power turn out; Reset timer; FoodInOut
Press the button		Lamp switch on; Power turn on; Timer +60s; Cooking	Timer +10 s; Cooking
Timer			Timer -1s; Cooking If (timer == 0) {Power turn out; Lamp switch off; Reset timer;} Stop

Заполняем таблицу состояний

Чтобы завершить проектирование нашего конечного автомата, необходимо продумать, как заполнить каждую пустую ячейку в этой таблице. Нужно для каждой ячейки решить, может ли данное событие произойти в этом состоянии, и если может, то какие действия должен выполнить объект в этой ситуации и каким должно быть следующее состояние. Это утомительная, но совершенно необходимая фаза процесса проектирования.

Порядок заполнения ячеек не имеет значения. Обычно к этому шагу в процессе разработки возвращаются неоднократно, еще и еще раз продумывая каждую ячейку, часто пересматривая ее содержимое, причем каждый раз по-новому. Нередки также добавления (или удаления) состояний по ходу процесса, что вызывает дальнейший пересмотр. Здесь не будем останавливаться на этих итерациях, подводя итог всему этапу проектирования и пересматривая результаты для всех состояний и событий по очереди.

Состояние FoodInOut

Во время этого состояния должно наступить только инициирующее событие Shutting the door, которое мы уже рассмотрели. Поэтому во всех остальных ячейках первого столбца можно написать «не должно наступить». В частности, событие Opening the door не имеет смысла, поскольку дверь и так открыта.

Состояние Stop

В этом состоянии дверь закрыта. При этом возможно как открытие двери, так и нажатие кнопки. Событие Shutting the door является невозможным, так как дверь закрыта.

Состояние Cooking

В этом состоянии возможны все события, кроме Shutting the door, поскольку дверь в этом состоянии также закрыта. Все остальные события возможны.

Событие Shutting the door

Данное событие возможно только в состоянии FoodInOut.

Событие Opening the door

Данное событие возможно в состояниях Stop и Cooking.

Отметим, что названные выше два события являются операциями, производимыми над дверцей. Кроме того, они являются взаимоисключающими. Поэтому эти два события можно объединить в одно событие, например, Get the door. Результат данного события будет зависеть от состояния.

Событие Press the button

Нажатие кнопки в состоянии Stop переводит объект в состояние Cooking и сопровождается действиями, которые мы определили выше. Нажатие кнопки в состоянии Cooking не меняет состояния, а лишь сопровождается увеличением показаний таймера. Если это событие произойдет в состоянии FoodInOut, то состояние не изменится.

Событие Timer

Данное событие возможно лишь в состоянии Cooking . Его описание также полностью определено и не нуждается в дополнении на данном этапе проектирования.

Результирующая диаграмма и таблица будут выглядеть так:

События\Состояния	FoodInOut	Stop	Cooking
Get the door	Lamp switch off; Stop	Lamp switch on; FoodInOut	Power turn out; Reset timer; FoodInOut
Press the button	FoodInOut	Lamp switch on; Power turn on; Timer +60s; Cooking	Timer +10 s; Cooking
Timer			Timer -1s; Cooking If (timer == 0) {Power turn out; Lamp switch off; Reset timer;} Stop

Составление списка переменных состояния

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

short int preparation_time; //текущее показание таймера на момент наблюдения (сколько времени осталось готовить пищу); значение нуль - питание выключено

bool current_lamp; // текущее состояние лампочки: true - включена, false - выключена

bool current_door; // текущее состояние дверцы: true - открыта, false - закрыта

bool current_power; //текущее состояние элемента питания: true - включен, false – выключен.

Таким образом, состояния определенного нами конечного автомата определены следующим образом:

FoodInOut: current_power=false; current_lamp=true; current_door=true; preparation_time=0;

Stop: current_power=false; current_lamp=false; current_door=false; preparation_time=0;

Cooking: current_power=true;current_lamp=true; current_door=false; preparation_time>0;

Рассмотрим теперь входной алфавит. Он содержит два входных символа, которые представляют описанные нами события: a₁=”Get the door”; a₂=”Press the button”. Событие Timer мы будем реализовывать отдельно.