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