Diagrama de estados

En informática y campos afines, los diagramas de estados se utilizan para describir el comportamiento de los sistemas. Estos diagramas requieren que el sistema esté compuesto por un número finito de estados . En ocasiones, esto se cumple, mientras que en otras se trata de una abstracción razonable . Existen diversas formas de diagramas de estados, que difieren ligeramente y poseen semánticas distintas .

Los diagramas de estados proporcionan una descripción abstracta del comportamiento de un sistema . Este comportamiento se analiza y representa mediante una serie de eventos que pueden ocurrir en uno o más estados posibles. En este sentido, "cada diagrama suele representar objetos de una sola clase y registra los diferentes estados de sus objetos a lo largo del sistema". ^{[ 1 ]}

Los diagramas de estados se pueden usar para representar gráficamente máquinas de estados finitos (también llamadas autómatas finitos). Esto fue introducido por Claude Shannon y Warren Weaver en su libro de 1949, The Mathematical Theory of Communication . Otra fuente es Taylor Booth en su libro de 1967, Sequential Machines and Automata Theory . Otra representación posible es la tabla de transición de estados .

Una forma clásica de diagrama de estados para un autómata finito (AF) es un grafo dirigido con los siguientes elementos (Q, Σ, Z, δ, q ₀ , F): ^{[ 2 ] [ 3 ]}

• Vértices Q : un conjunto finito de estados, normalmente representados por círculos y etiquetados con símbolos designadores únicos o palabras escritas en su interior.
• Símbolos de entrada Σ : una colección finita de símbolos o designadores de entrada.
• Símbolos de salida Z : una colección finita de símbolos o designadores de salida.

La función de salida ω representa el mapeo de pares ordenados de símbolos de entrada y estados sobre símbolos de salida, denotado matemáticamente como ω  : Σ × Q → Z .

• Edges δ: represent transitions from one state to another as caused by the input (identified by their symbols drawn on the edges). An edge is usually drawn as an arrow directed from the present state to the next state. This mapping describes the state transition caused by an input. This is written mathematically as δ : Q × Σ → Q, so δ (the transition function) in the definition of the FA is given by both the pair of vertices connected by an edge and the symbol on an edge in a diagram representing this FA. Item δ(q, a) = p in the definition of the FA means that from the state named q under input symbol a, the transition to the state p occurs in this machine. In the diagram representing this FA, this is represented by an edge labeled by a pointing from the vertex labeled by q to the vertex labeled by p.
• Start state q₀: (not shown in the examples below). The start state q₀ ∈ Q is usually represented by an arrow with no origin pointing to the state. In older texts,^[2][4] the start state is not shown and must be inferred from the text.
• Accepting state(s) F: If used, for example for accepting automata, F ∈ Q is the accepting state. It is usually drawn as a double circle. Sometimes the accept state(s) function as "Final" (halt, trapped) states.^[3]

For a deterministic finite automaton (DFA), nondeterministic finite automaton (NFA), generalized nondeterministic finite automaton (GNFA), or Moore machine, the input is denoted on each edge. For a Mealy machine, input and output are signified on each edge, separated with a slash "/": "1/0" denotes the state change upon encountering the symbol "1" causing the symbol "0" to be output. For a Moore machine the state's output is usually written inside the state's circle, also separated from the state's designator with a slash "/". There are also variants that combine these two notations.

For example, if a state has a number of outputs (e.g. "a= motor counter-clockwise=1, b= caution light inactive=0") the diagram should reflect this : e.g. "q5/1,0" designates state q5 with outputs a=1, b=0. This designator will be written inside the state's circle.

Los diagramas de estados de Harel, ^{[ 5 ]} inventados por el científico informático David Harel , están ganando popularidad desde que una variante se incorporó al Lenguaje Unificado de Modelado (UML). Este tipo de diagrama permite modelar superestados , regiones ortogonales y actividades como parte de un estado.

Los diagramas de estados clásicos requieren la creación de nodos distintos para cada combinación válida de parámetros que definen el estado. Salvo en los sistemas más sencillos, esto puede generar un gran número de nodos y transiciones entre ellos ( explosión de estados y transiciones ), lo que reduce la legibilidad del diagrama. Con los diagramas de estados de Harel, es posible modelar múltiples diagramas de estados multifuncionales dentro del mismo diagrama. Cada una de estas máquinas de estados multifuncionales puede realizar transiciones internas sin afectar a las demás. El estado actual de cada máquina de estados multifuncional define el estado del sistema. El diagrama de estados de Harel es equivalente a un diagrama de estados, pero mejora su legibilidad.

Existen otros conjuntos de semántica disponibles para representar diagramas de estados. Por ejemplo, hay herramientas para modelar y diseñar la lógica de los controladores embebidos. ^{[ 6 ]} Estos diagramas, al igual que las máquinas de estados originales de Harel, ^{[ 7 ]} admiten estados anidados jerárquicamente, regiones ortogonales, acciones de estado y acciones de transición. ^{[ 8 ]}

Quienes se inician en el formalismo de las máquinas de estados suelen confundir los diagramas de estados con los diagramas de flujo . La siguiente figura muestra una comparación entre un diagrama de estados y un diagrama de flujo. Una máquina de estados (panel (a)) realiza acciones en respuesta a eventos explícitos. En cambio, el diagrama de flujo (panel (b)) transita automáticamente de un nodo a otro al completar las actividades. ^{[ 9 ]}

Los nodos de los diagramas de flujo son aristas en el grafo de estados resultante. Esto se debe a que cada nodo representa un comando del programa. Un comando es una acción que se ejecuta. Un comando no es un estado, pero al aplicarse al estado del programa, provoca una transición a otro estado.

En detalle, el listado del código fuente representa un grafo de programa. La ejecución de este grafo (análisis e interpretación) genera un grafo de estados. Por lo tanto, cada grafo de programa genera un grafo de estados. La conversión del grafo de programa a su grafo de estados asociado se denomina "despliegue" del grafo de programa.

El grafo del programa es una secuencia de comandos. Si no existen variables, el estado consiste únicamente en el contador del programa, que registra la posición del programa durante la ejecución (cuál es el siguiente comando que se aplicará).

Antes de ejecutar un comando, el contador de programa se encuentra en una posición determinada (estado previo a la ejecución del comando). La ejecución del comando desplaza el contador de programa al siguiente comando. Dado que el contador de programa representa el estado completo, la ejecución del comando modifica dicho estado. Por lo tanto, el comando en sí mismo corresponde a una transición entre los dos estados.

Consideremos ahora el caso completo, donde existen variables y se ven afectadas por los comandos del programa que se ejecutan. No solo cambia el contador de programa entre distintas ubicaciones, sino que las variables también pueden cambiar de valor debido a los comandos ejecutados. Por consiguiente, incluso si volvemos a ejecutar algún comando del programa (por ejemplo, dentro de un bucle), esto no implica que el programa se encuentre en el mismo estado.

En el caso anterior, el programa estaría en el mismo estado porque todo el estado se reduce al contador del programa. Por lo tanto, si el programa apunta a la misma posición (siguiente comando), basta con especificar que estamos en el mismo estado. Sin embargo, si el estado incluye variables que cambian de valor, podemos estar en la misma ubicación del programa con valores de variables diferentes, lo que significa estar en un estado distinto en el espacio de estados del programa. El término "despliegue" proviene de esta multiplicación de ubicaciones al generar el grafo de estados a partir del grafo del programa.

Una autotransición es una transición en la que el estado inicial y el estado final son iguales.

Un ejemplo representativo es un bucle `do` que incrementa un contador hasta que se desborda y vuelve a cero. Aunque el bucle `do` ejecuta el mismo comando de incremento iterativamente, su espacio de estados no es un ciclo, sino una línea. Esto se debe a que el estado es la ubicación del programa (en este caso, el ciclo) combinada con el valor del contador, que aumenta de forma constante (hasta el desbordamiento). Por lo tanto, se visitan diferentes estados en secuencia hasta que se produce el desbordamiento. Tras el desbordamiento, el contador vuelve a cero, por lo que se vuelve a visitar el estado inicial en el espacio de estados, cerrando así un ciclo (suponiendo que el contador se inicializó a cero).

La figura anterior intenta mostrar esa inversión de roles alineando los arcos de los diagramas de estado con las etapas de procesamiento del diagrama de flujo.

Un diagrama de flujo se puede comparar con una línea de montaje en la fabricación, ya que describe la progresión de una tarea desde el principio hasta el final (por ejemplo, la transformación del código fuente en código objeto mediante un compilador). Una máquina de estados, en general, no contempla dicha progresión. El ejemplo de la máquina de estados de la puerta que se muestra arriba no se encuentra en una etapa más avanzada en el estado "cerrado" que en el estado "abierto". Simplemente reacciona de forma diferente a los eventos de apertura y cierre. En una máquina de estados, un estado es una forma eficiente de especificar un comportamiento, en lugar de una etapa de procesamiento.

Una extensión interesante consiste en permitir que los arcos fluyan desde cualquier número de estados a cualquier número de estados. Esto solo tiene sentido si el sistema puede estar en múltiples estados a la vez, lo que implica que un estado individual solo describe una condición u otro aspecto parcial del estado global. El formalismo resultante se conoce como red de Petri .

Otra extensión permite la integración de diagramas de flujo dentro de los diagramas de estados de Harel. Esta extensión admite el desarrollo de software que se basa tanto en eventos como en flujos de trabajo.

• David Harel
• DRAGÓN
• SCXML es un lenguaje XML que proporciona un entorno de ejecución genérico basado en máquinas de estados, utilizando diagramas de estados de Harel.
• Máquina de estados UML
• YAKINDU Statechart Tools es un software para modelar diagramas de estados (diagramas de estados de Harel, máquinas de Mealy, máquinas de Moore), realizar simulaciones y generar código fuente.

• statecharts.online Tutorial completo e interactivo sobre diagramas de estados y máquinas de estados
• Introducción a los diagramas de máquinas de estados UML 2 por Scott W. Ambler
• Guía para diagramas de máquinas de estados UML 2 por Scott W. Ambler
• Intelliwizard - UML StateWizard - Un marco y herramienta de modelado/desarrollo dinámico UML de ida y vuelta, ya descontinuado, que se ejecutaba en IDE populares bajo una licencia de código abierto.
• YAKINDU Statechart Tools : una herramienta de código abierto para la especificación y el desarrollo de sistemas reactivos basados ​​en eventos con la ayuda de máquinas de estados .
• Comprensión y uso de las máquinas de estados: Charlas técnicas de MATLAB sobre máquinas de estados
• FSM: Generación de máquinas de estados finitos de código abierto en Java por Alexander Sakharov FSM
• scxmlcc Un compilador eficiente de máquina de estados scxml a C++.
• SMC: Un compilador de máquinas de estados de código abierto que genera máquinas de estados finitos para muchos lenguajes como C, Python, Lua, Scala, PHP, Java, VB, etc. SMC