Диаграмма состояний используется в информатике и смежных областях для описания поведения систем. Диаграммы состояний требуют, чтобы система состояла из конечного числа состояний . Иногда это действительно так, а в других случаях это разумная абстракция . Существует много форм диаграмм состояний, которые немного отличаются и имеют разную семантику .
Диаграммы состояний предоставляют абстрактное описание поведения системы . Это поведение анализируется и представляется серией событий, которые могут происходить в одном или нескольких возможных состояниях. При этом «каждая диаграмма обычно представляет объекты одного класса и отслеживает различные состояния его объектов через систему». [1]
Диаграммы состояний можно использовать для графического представления конечных автоматов (также называемых конечными автоматами). Это было введено Клодом Шенноном и Уорреном Уивером в их книге 1949 года «Математическая теория связи» . Другим источником является Тейлор Бут в его книге 1967 года «Последовательные машины и теория автоматов» . Другим возможным представлением является таблица переходов состояний .
Классической формой диаграммы состояний конечного автомата (КА) является ориентированный граф со следующими элементами (Q, Σ, Z, δ, q 0 , F): [2] [3]
Выходная функция ω представляет собой отображение упорядоченных пар входных символов и состояний на выходные символы, обозначаемое математически как ω : Σ × Q → Z .
Для детерминированного конечного автомата (DFA), недетерминированного конечного автомата (NFA), обобщенного недетерминированного конечного автомата (GNFA) или машины Мура вход обозначается на каждом ребре. Для машины Мили вход и выход обозначаются на каждом ребре, разделенные косой чертой "/": "1/0" обозначает изменение состояния при встрече символа "1", вызывающее вывод символа "0". Для машины Мура выход состояния обычно записывается внутри круга состояния, также отделенного от обозначения состояния косой чертой "/". Существуют также варианты, которые объединяют эти две нотации.
Например, если состояние имеет несколько выходов (например, "a= двигатель против часовой стрелки=1, b= предупреждающий свет выключен=0"), диаграмма должна это отражать: например, "q5/1,0" обозначает состояние q5 с выходами a=1, b=0. Это обозначение будет записано внутри круга состояния.
S 1 и S 2 — это состояния, а S 1 — это принимающее состояние или конечное состояние . Каждое ребро помечено входом. В этом примере показан акцептор для двоичных чисел, содержащих четное количество нулей.
S 0 , S 1 и S 2 — состояния. Каждое ребро помечено как « j / k », где j — вход, а k — выход.
Диаграммы состояний Харела [5] , изобретенные ученым-компьютерщиком Дэвидом Харелом , получают широкое распространение с тех пор, как один из вариантов стал частью унифицированного языка моделирования (UML). [ необходим неосновной источник ] Этот тип диаграмм позволяет моделировать суперсостояния , ортогональные области и действия как часть состояния.
Классические диаграммы состояний требуют создания отдельных узлов для каждой допустимой комбинации параметров, определяющих состояние. Для всех систем, кроме самых простых, это может привести к очень большому количеству узлов и переходов между узлами ( взрыв состояний и переходов ), что снижает читаемость диаграммы состояний. С помощью диаграмм состояний Harel можно моделировать несколько кросс-функциональных диаграмм состояний в диаграмме состояний. Каждая из этих кросс-функциональных машин состояний может переходить внутренне, не влияя на другие машины состояний. Текущее состояние каждой кросс-функциональной машины состояний определяет состояние системы. Диаграмма состояний Harel эквивалентна диаграмме состояний, но улучшает ее читаемость.
Существуют и другие наборы семантики, доступные для представления диаграмм состояний. Например, существуют инструменты для моделирования и проектирования логики для встроенных контроллеров. [6] Эти диаграммы, как и оригинальные конечные автоматы Харела, [7] поддерживают иерархически вложенные состояния, ортогональные области, действия состояний и действия переходов. [8]
Новички в формализме конечного автомата часто путают диаграммы состояний с блок-схемами . На рисунке ниже показано сравнение диаграммы состояний с блок-схемой. Конечный автомат (панель (a)) выполняет действия в ответ на явные события. Напротив, блок-схема (панель (b)) автоматически переходит от узла к узлу после завершения действий. [9]
Узлы блок-схем являются ребрами в индуцированном графе состояний. Причина в том, что каждый узел в блок-схеме представляет собой команду программы. Команда программы — это действие, которое должно быть выполнено. Команда не является состоянием, но при применении к состоянию программы вызывает переход в другое состояние.
Более подробно, листинг исходного кода представляет собой программный граф. Выполнение программного графа (анализ и интерпретация) приводит к графу состояний. Таким образом, каждый программный граф порождает граф состояний. Преобразование программного графа в его ассоциированный граф состояний называется «развертыванием» программного графа.
Граф программы представляет собой последовательность команд. Если переменных не существует, то состояние состоит только из счетчика программы, который отслеживает местоположение программы во время выполнения (какая следующая команда будет применена).
Перед выполнением команды счетчик программ находится в некоторой позиции (состояние до выполнения команды). Выполнение команды перемещает счетчик программ на следующую команду. Поскольку счетчик программ — это все состояние, выполнение команды изменило состояние. Таким образом, сама команда соответствует переходу между двумя состояниями.
Теперь рассмотрим полный случай, когда переменные существуют и на них влияют выполняемые команды программы. Не только счетчик программы меняется между различными местоположениями счетчика программы, но и переменные могут также менять значения из-за выполняемых команд. Следовательно, даже если мы повторно посещаем какую-то команду программы (например, в цикле), это не означает, что программа находится в том же состоянии.
В предыдущем случае программа находилась бы в том же состоянии, поскольку все состояние — это просто счетчик программы. Таким образом, если программа указывает на ту же позицию (следующая команда), достаточно указать, что мы находимся в том же состоянии. Однако, если состояние включает переменные, которые меняют значение, мы можем находиться в том же месте программы с разными значениями переменных, то есть в другом состоянии в пространстве состояний программы. Термин «развертывание» происходит от этого умножения мест при создании графа состояний из графа программы.
Самопереход — это переход, при котором начальное и конечное состояние совпадают.
Типичным примером является цикл do, увеличивающий некоторый счетчик до тех пор, пока он не переполнится и снова не станет равным 0. Хотя цикл do итеративно выполняет ту же команду увеличения, его пространство состояний представляет собой не цикл, а строку. Это происходит из-за того, что состояние является местоположением программы (здесь циклично) в сочетании со значением счетчика, которое строго увеличивается (до переполнения). Таким образом, различные состояния посещаются последовательно, пока не произойдет переполнение. После переполнения счетчик снова становится равным 0, поэтому начальное состояние повторно посещается в пространстве состояний, замыкая цикл в пространстве состояний (предполагая, что счетчик был инициализирован в 0).
На рисунке выше предпринята попытка показать эту смену ролей путем сопоставления дуг диаграмм состояний с этапами обработки блок-схемы.
Можно сравнить блок-схему с конвейером в производстве, поскольку блок-схема описывает ход выполнения некоторой задачи от начала до конца (например, преобразование входного исходного кода в выходной объектный код компилятором). Конечный автомат, как правило, не имеет понятия о таком ходе. Приведенный выше пример конечного автомата двери не находится на более продвинутой стадии в состоянии «закрыто», чем в состоянии «открыто». Скорее, он просто по-разному реагирует на события открытия/закрытия. Состояние в конечном автомате — это эффективный способ указания поведения, а не этап обработки.
Интересное расширение — разрешить дугам перетекать из любого количества состояний в любое количество состояний. Это имеет смысл только в том случае, если системе разрешено находиться в нескольких состояниях одновременно, что подразумевает, что отдельное состояние описывает только условие или другой частичный аспект общего, глобального состояния. Полученный формализм известен как сеть Петри .
Другое расширение позволяет интегрировать блок-схемы в диаграммы состояний Harel. Это расширение поддерживает разработку программного обеспечения, которое управляется как событиями, так и рабочими процессами.
