Диаграмма состояний представляет собой тип диаграммы , используемой в информатике и смежных областях , чтобы описать поведение системы. Диаграммы состояний требуют, чтобы описываемая система состояла из конечного числа состояний ; иногда это действительно так, а иногда это разумная абстракция . Существует множество форм диаграмм состояний, которые немного отличаются и имеют разную семантику .
Обзор
Диаграммы состояний используются , чтобы дать абстрактное описание поведения в виде системы . Это поведение анализируется и представляется серией событий, которые могут происходить в одном или нескольких возможных состояниях. Таким образом, «каждая диаграмма обычно представляет объекты одного класса и отслеживает различные состояния его объектов в системе». [1]
Диаграммы состояний могут использоваться для графического представления конечных автоматов (также называемых конечными автоматами). Это было введено Клодом Шенноном и Уорреном Уивером в их книге 1949 года «Математическая теория коммуникации» . Другой источник - Тейлор Бут в его книге 1967 года « Последовательные машины и теория автоматов» . Другое возможное представление - таблица переходов между состояниями .
Направленный граф
Классическая форма диаграммы состояний конечного автомата (FA) - ориентированный граф со следующими элементами (Q, Σ, Z, δ, q 0 , F): [2] [3]
- Вершины Q : конечный набор состояний, обычно представленных кружками и помеченных уникальными обозначениями или словами, написанными внутри них.
- Входные символы Σ : конечный набор входных символов или обозначений.
- Выходные символы Z : конечный набор выходных символов или обозначений
Выходная функция ω представляет собой отображение упорядоченных пары входных символов и состояний на выходные символы, обозначаемые математически со : Σ × Q → Z .
- Ребра δ : представляют переходы из одного состояния в другое, вызванные вводом (обозначены их символами, нарисованными на краях). Ребро обычно изображается в виде стрелки, направленной от текущего состояния к следующему состоянию. Это отображение описывает переход состояния, который должен произойти при вводе определенного символа. Математически это записывается как δ : Q × Σ → Q , поэтому δ (функция перехода) в определении FA задается как парой вершин, соединенных ребром, так и символом на ребре на диаграмме, представляющей эту FA. . Пункт δ (q, a) = p в определении FA означает, что из состояния с именем q под входным символом a в этой машине происходит переход в состояние p . На схеме , изображающей эту FA, это представлено ребром , помеченном в указывающем от вершины , помеченной д к вершине , помеченной р .
- Состояние запуска q 0 : (не показано в примерах ниже). Начальное состояние q 0 ∈ Q обычно представлено стрелкой без начала координат, указывающей на состояние. В старых текстах [2] [4] начальное состояние не отображается и должно выводиться из текста.
- Состояние приема F : Если используется, например, для приема автоматов, F ∈ Q является состоянием приема . Обычно его рисуют в виде двойного круга. Иногда принимает государственную функцию (ы) в качестве « F ынал» (Стойте, запертые) состояний. [3]
Для детерминированного конечного автомата (DFA), недетерминированного конечного автомата (NFA), обобщенного недетерминированного конечного автомата (GNFA) или машины Мура вход обозначается на каждом ребре. Для машины Мили вход и выход обозначены на каждом краю, разделены косой чертой «/»: «1/0» обозначает изменение состояния при встрече с символом «1», вызывающее вывод символа «0». Для машины Мура выходные данные состояния обычно записываются внутри круга состояния, также отделенного от обозначения состояния косой чертой «/». Есть также варианты, сочетающие эти два обозначения.
Например, если состояние имеет несколько выходов (например, «a = двигатель против часовой стрелки = 1, b = сигнальная лампа неактивна = 0») диаграмма должна отражать это: например, «q5 / 1,0» обозначает состояние q5 с выводит a = 1, b = 0. Это обозначение будет написано внутри круга государства.
Пример: DFA, NFA, GNFA или машина Мура.
S 1 и S 2 являются состояниями, а S 1 - состоянием приема или конечным состоянием . Каждое ребро помечено входом. В этом примере показан акцептор для двоичных чисел, содержащих четное количество нулей.
Пример: машина для мучных работ
S 0 , S 1 и S 2 - состояния. Каждое ребро помечено « j / k », где j - вход, а k - выход.
Диаграмма состояний Харела
Диаграммы состояний Харела [5], изобретенные компьютерным ученым Дэвидом Харелом , получают широкое распространение, поскольку их вариант стал частью унифицированного языка моделирования (UML). [ Требуется неосновной источник ] Тип диаграммы позволяет моделировать суперсостояния , ортогональные области и действия как часть состояния.
Классические диаграммы состояний требуют создания отдельных узлов для каждой допустимой комбинации параметров, определяющих состояние. Это может привести к очень большому количеству узлов и переходов между узлами для всех систем, кроме простейших ( взрыв состояний и переходов ). Эта сложность снижает удобочитаемость диаграммы состояний. С помощью диаграмм состояний Harel можно моделировать несколько диаграмм кросс-функциональных состояний внутри диаграммы состояний. Каждый из этих универсальных конечных автоматов может выполнять внутренний переход, не затрагивая другие конечные автоматы в диаграмме состояний. Текущее состояние каждого универсального конечного автомата в диаграмме состояний определяет состояние системы. Диаграмма состояний Харела эквивалентна диаграмме состояний, но улучшает читаемость полученной диаграммы.
Альтернативная семантика
Доступны и другие наборы семантики для представления диаграмм состояний. Например, есть инструменты для моделирования и проектирования логики для встраиваемых контроллеров. [6] Эти диаграммы, как и оригинальные конечные автоматы Харела, [7] поддерживают иерархически вложенные состояния, ортогональные области, действия состояния и действия перехода. [8]
Диаграммы состояний в сравнении с блок-схемами
Новички в формализме конечного автомата часто путают диаграммы состояний с блок- схемами . На рисунке ниже показано сравнение диаграммы состояний с блок-схемой. Конечный автомат (панель (а)) выполняет действия в ответ на явные события. В отличие от этого, блок-схема (панель (b)) не требует явных событий, а скорее переходит от узла к узлу в своем графе автоматически после завершения действий. [9]
Узлы блок-схем - это ребра в индуцированном графе состояний. Причина в том, что каждый узел в блок-схеме представляет собой команду программы. Программная команда - это действие, которое нужно выполнить. Таким образом, это не состояние, но когда оно применяется к состоянию программы, оно приводит к переходу в другое состояние.
Более подробно, листинг исходного кода представляет собой граф программы. Выполнение графа программы (синтаксический анализ и интерпретация) приводит к графу состояний. Таким образом, каждый граф программы порождает граф состояний. Преобразование графа программы в связанный с ним граф состояний называется «разворачиванием» графа программы.
Граф программы представляет собой последовательность команд. Если никаких переменных не существует, то состояние состоит только из программного счетчика, который отслеживает, где в программе мы находимся во время выполнения (какая следующая команда будет применена).
В этом случае перед выполнением команды счетчик программы находится в некоторой позиции (состояние до выполнения команды). Выполнение команды перемещает счетчик программы к следующей команде. Поскольку счетчик программы - это все состояние, отсюда следует, что выполнение команды изменило состояние. Таким образом, сама команда соответствует переходу между двумя состояниями.
Теперь рассмотрим полный случай, когда переменные существуют и на них влияют выполняемые команды программы. Затем между различными ячейками счетчика программы не только изменяется счетчик программы, но и переменные могут также изменять значения из-за выполненных команд. Следовательно, даже если мы повторно обратимся к какой-либо команде программы (например, в цикле), это не означает, что программа находится в том же состоянии.
В предыдущем случае программа была бы в том же состоянии, потому что все состояние - это просто счетчик программы, поэтому, если программа указывает на ту же позицию (следующая команда), достаточно указать, что мы находимся в том же состоянии. Однако, если состояние включает переменные, то, если они изменяют значение, мы можем находиться в том же месте программы с разными значениями переменных, то есть в другом состоянии в пространстве состояний программы. Термин «разворачивание» происходит от этого умножения местоположений при создании графа состояний из графа программы.
Самостоятельный переход - это переход, в котором начальное и конечное состояние совпадают.
Типичным примером является цикл do, увеличивающий некоторый счетчик до тех пор, пока он не переполнится и снова не станет 0. Хотя цикл do итеративно выполняет одну и ту же команду приращения, поэтому граф программы выполняет цикл, в его пространстве состояний находится не цикл, а строка. Это происходит из-за того, что состояние является местоположением программы (здесь цикл) в сочетании со значением счетчика, которое строго увеличивается (до переполнения), поэтому различные состояния посещаются последовательно, до переполнения. После переполнения счетчик снова становится 0, поэтому начальное состояние повторно посещается в пространстве состояний, закрывая цикл в пространстве состояний (при условии, что счетчик был инициализирован на 0).
На рисунке выше делается попытка показать эту смену ролей путем совмещения дуг диаграмм состояний с этапами обработки блок-схемы.
Вы можете сравнить блок-схему с производственной линией, потому что блок-схема описывает продвижение некоторой задачи от начала до конца (например, преобразование входного исходного кода в выходной объектный код компилятором). Конечный автомат обычно не имеет представления о таком прогрессе. Конечный автомат двери, показанный в верхней части этой статьи, например, не находится на более продвинутой стадии, когда он находится в состоянии «закрыто», по сравнению с состоянием «открыто»; он просто по-разному реагирует на события открытия / закрытия. Состояние в конечном автомате - это эффективный способ определения определенного поведения, а не этап обработки.
Прочие расширения
Интересным расширением является разрешение дугам переходить из любого количества состояний в любое количество состояний. Это имеет смысл только в том случае, если системе разрешено находиться в нескольких состояниях одновременно, что означает, что отдельное состояние описывает только условие или другой частичный аспект общего глобального состояния. Полученный формализм известен как сеть Петри .
Другое расширение позволяет интегрировать блок-схемы в диаграммы состояний Harel. Это расширение поддерживает разработку программного обеспечения, которое управляется как событиями, так и рабочими процессами.
Смотрите также
- Дэвид Харел
- ДРАКОН
- SCXML - язык XML, который обеспечивает общую среду выполнения на основе конечного автомата, основанную на диаграммах состояний Харела.
- Конечный автомат UML
- YAKINDU Statechart Tools - это программное обеспечение для моделирования диаграмм состояний (диаграммы состояний Харела, машины Мили, машины Мура), моделирования и генерации исходного кода.
Рекомендации
- ^ Архивный указатель на Wayback Machine
- ^ a b Тейлор Бут (1967) Теория последовательных машин и автоматов , Джон Уайли и сыновья, Нью-Йорк.
- ^ a b Джон Хопкрофт и Джеффри Уллман (1979) Введение в теорию автоматов, языки и вычисления , издательство Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X
- ↑ Эдвард Дж. МакКласки , Введение в теорию коммутационных цепей, McGraw-Hill, 1965
- ^ Дэвид Харел , диаграммы состояний: визуальный формализм для сложных систем. Наука компьютерного программирования , 8 (3): 231–274, июнь 1987.
- ^ Тивари, A. (2002). Формальная семантика и методы анализа для Simulink Stateflow.
- Перейти ↑ Harel, D. (1987). Визуальный формализм для сложных систем. Наука компьютерного программирования, 231–274.
- ^ Алур, Р., Kanade А., Рамеш, S., & Shashidhar, KC (2008). Символьный анализ для улучшения покрытия симуляцией моделей Simulink / Stateflow. Международная конференция по встроенному программному обеспечению (стр. 89–98). Атланта, Джорджия: ACM.
- ^ Самек, Миро (2008). Практические диаграммы состояний UML на C / C ++, второе издание: событийно-ориентированное программирование для встроенных систем . Newnes. п. 728. ISBN 978-0-7506-8706-5.
Внешние ссылки
- Введение в диаграммы конечных автоматов UML 2 , Скотт У. Амблер
- Рекомендации по диаграммам конечных автоматов UML 2 , Скотт У. Амблер
- Intelliwizard - UML StateWizard - похожий на ClassWizard фреймворк для динамического моделирования / разработки UML и инструмент, работающий в популярных IDE под лицензией с открытым исходным кодом.
- YAKINDU Statechart Tools - инструмент с открытым исходным кодом для спецификации и разработки реактивных, управляемых событиями систем с помощью конечных автоматов .
- Понимание и использование государственных машин MATLAB Tech Talks о государственных машинах
- FSM: Генерация конечных автоматов с открытым исходным кодом на Java от Александра Сахарова FSM
- scxmlcc Эффективный конечный автомат scxml для компилятора C ++.
- SMC: компилятор конечного автомата с открытым исходным кодом, который генерирует FSM для многих языков, таких как C, Python, Lua, Scala, PHP, Java, VB и т. Д. SMC
- Диаграмма состояний - бесплатная библиотека C ++ с открытым исходным кодом, которая поддерживает определение и выполнение конечных автоматов, содержащих иерархию и параллелизм.