Диаграммы состояний конечных автоматов

Введение

Диаграмма поведения конечных автоматов

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

Обзор

Диаграммы состояний предоставляют абстрактное описание поведения системы. Это поведение анализируется и представляется серией событий, которые могут произойти в одном или нескольких возможных состояниях. При этом "каждая диаграмма обычно представляет объекты одного класса и отслеживает различные состояния этих объектов в системе". Диаграммы состояний могут использоваться для графического представления конечных автоматов (также называемых конечными автоматами). Эта концепция была введена Клодом Шенноном и Уорреном Уивером в их книге 1949 года «Математическая теория коммуникации». Другим источником является Тейлор Бут в его книге 1967 года «Последовательные машины и теория автоматов». Альтернативным представлением является таблица переходов состояний.

Альтернативная семантика

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

Диаграммы состояния против блок-схемы

Новички в формализме машины состояний часто путают диаграммы состояний с блок-схемами. На рисунке ниже показано сравнение диаграммы состояний и блок-схемы. Машина состояний (панель (a)) выполняет действия в ответ на явные события. В отличие от этого, блок-схема (панель (b)) автоматически переходит от узла к узлу после завершения операций. Узлы блок-схемы являются ребрами в порожденном графе состояний. Причина в том, что каждый узел в блок-схеме представляет команду программы. Команда программы – это действие, которое должно быть выполнено. Команда не является состоянием, но при применении к состоянию программы вызывает переход в другое состояние. Более подробно, исходный код представляет собой граф программы. Выполнение графа программы (разбор и интерпретация) приводит к графу состояний. Таким образом, каждый граф программы порождает граф состояний. Преобразование графа программы в соответствующий граф состояний называется "развертыванием" графа программы. Граф программы – это последовательность команд. Если переменных не существует, то состояние состоит только из счетчика команд, который отслеживает местоположение программы во время выполнения (какая следующая команда будет применена). Перед выполнением команды счетчик команд находится в определенной позиции (состояние перед выполнением команды). Выполнение команды перемещает счетчик команд к следующей команде. Поскольку счетчик команд и есть все состояние, выполнение команды изменило состояние. Таким образом, сама команда соответствует переходу между двумя состояниями. Теперь рассмотрим полный случай, когда существуют переменные, на которые влияют выполняемые команды программы. Не только счетчик команд меняется между различными позициями, но и переменные могут менять значения из-за выполняемых команд. Следовательно, даже если мы повторно посетим какую-то команду программы (например, в цикле), это не означает, что программа находится в том же состоянии. В предыдущем случае программа была бы в том же состоянии, потому что все состояние – это просто счетчик команд. Таким образом, если счетчик команд указывает на ту же позицию (следующую команду), достаточно указать, что мы находимся в том же состоянии. Однако, если состояние включает переменные, которые меняют значение, мы можем быть в одном и том же месте программы с разными значениями переменных, то есть в другом состоянии в пространстве состояний программы. Термин "развертывание" происходит от этого умножения позиций при создании графа состояний из графа программы. Самопереход – это переход, когда начальное и конечное состояние одинаковы. Типичным примером является цикл do, увеличивающий какой-то счетчик до тех пор, пока он не переполнится и снова не станет 0. Хотя цикл do выполняет одну и ту же команду инкремента итеративно, его пространство состояний не является циклом, а линией. Это происходит из-за того, что состояние определяется местоположением программы (здесь циклическим) в сочетании со значением счетчика, которое строго возрастает (до переполнения). Таким образом, различные состояния посещаются последовательно, пока не произойдет переполнение. После переполнения счетчик снова становится 0, поэтому начальное состояние возобновляется в пространстве состояний, замыкая цикл в пространстве состояний (при условии, что счетчик был инициализирован нулем). Рисунок выше пытается показать обращение ролей, выравнивая дуги диаграмм состояний с этапами обработки блок-схемы. Можно сравнить блок-схему с конвейером в производстве, поскольку блок-схема описывает прогрессию какой-либо задачи от начала до конца (например, преобразование исходного кода во входные данные в объектный код на выходе компилятором). Машина состояний, как правило, не имеет представления о такой прогрессии. Пример машины состояний двери, приведенный выше, не находится в более продвинутой стадии в "закрытом" состоянии, чем в "открытом". Скорее, он просто по-разному реагирует на события открытия/закрытия. Состояние в машине состояний – это эффективный способ определения поведения, а не этап обработки.

Newcomers to the state machine formalism often confuse state diagrams with flowcharts. The figure below shows a comparison of a state diagram with a flowchart. A state machine (panel (a)) performs actions in response to explicit events. In contrast, the flowchart (panel (b)) automatically transitions from node to node upon completion of activities. Nodes of flowcharts are edges in the induced graph of states. The reason is that each node in a flowchart represents a program command. A program command is an action to be executed. A command is not a state, but when applied to the program's state, causes a transition to another state. In more detail, the source code listing represents a program graph. Executing the program graph (parsing and interpreting) results in a state graph. So each program graph induces a state graph. Conversion of the program graph to its associated state graph is called "unfolding" of the program graph. The program graph is a sequence of commands. If no variables exist, then the state consists only of the program counter, which keeps track of program location during execution (what is the next command to be applied). Before executing a command, the program counter is at some position (state before the command is executed). Executing the command moves the program counter to the next command. Since the program counter is the whole state, executing the command changed the state. Thus, the command itself corresponds to a transition between the two states. Now consider the full case, when variables exist and are affected by the program commands being executed. Not only does the program counter change between different program counter locations, but variables might also change values due to the commands executed. Consequently, even if we revisit some program command (e. g. in a loop), this does not imply the program is in the same state. In the previous case, the program would be in the same state because the whole state is just the program counter. Thus, if the program counterpoints to the same position (next command) it suffices to specify that we are in the same state. However, if the state includes variables that change value, we can be at the same program location with different variable values, meaning in a different state in the program's state space. The term "unfolding" originates from this multiplication of locations when producing the state graph from the program graph. A self transition is a transition where the initial and the final state are the same. A representative example is a do loop incrementing some counter until it overflows and becomes 0 again. Although the do loop executes the same increment command iteratively, its state space is not a cycle but a line. This results from the state being the program location (here cycling) combined with the counter value, which is strictly increasing (until the overflow). Thus, different states are visited in sequence until the overflow occurs. After the overflow the counter becomes 0 again, so the initial state is revisited in the state space, closing a cycle in the state space (assuming the counter was initialized to 0). The figure above attempts to show that reversal of roles by aligning the arcs of the state diagrams with the processing stages of the flowchart. One can compare a flowchart to an assembly line in manufacturing because the flowchart describes the progression of some task from beginning to end (e. g., transforming source code input into object code output by a compiler). A state machine generally has no notion of such a progression. The door state machine example shown above is not in a more advanced stage in the "closed" state than in the "opened" state. Rather, it simply reacts differently to the open/close events. A state in a state machine is an efficient way of specifying a behavior, rather than a stage of processing.

Другие расширения

Интересное расширение заключается в том, чтобы позволить дугам переходить из любого числа состояний в любое число состояний. Это имеет смысл только в том случае, если системе разрешено одновременно находиться в нескольких состояниях, что означает, что отдельное состояние описывает лишь условие или другой частичный аспект общего, глобального состояния. Получающийся формализм известен как сеть Петри. Другое расширение позволяет интегрировать блок-схемы в диаграммы состояний Харела. Это расширение поддерживает разработку программного обеспечения, которое управляется как событиями, так и потоками работ.