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 .

• Las aristas δ representan transiciones de un estado a otro causadas por la entrada (identificadas por los símbolos dibujados en las aristas). Una arista se dibuja generalmente como una flecha que apunta desde el estado actual al siguiente. Este mapeo describe la transición de estado causada por una entrada. Esto se escribe matemáticamente como δ  : Q × Σ → Q , por lo que δ (la función de transición) en la definición del FA viene dada tanto por el par de vértices conectados por una arista como por el símbolo en una arista en un diagrama que representa este FA. El elemento δ(q, a) = p en la definición del FA significa que desde el estado llamado q bajo el símbolo de entrada a , la transición al estado p ocurre en esta máquina. En el diagrama que representa este FA, esto se representa mediante una arista etiquetada con a que apunta desde el vértice etiquetado con q al vértice etiquetado con p .
• Estado inicial q ₀ : (no se muestra en los ejemplos siguientes). El estado inicial q ₀ ∈ Q se suele representar mediante una flecha sin origen que apunta al estado. En textos más antiguos, ^{[ 2 ] [ 4 ]} el estado inicial no se muestra y debe inferirse del texto.
• Estado(s) de aceptación F : Si se utiliza, por ejemplo, para autómatas de aceptación, F ∈ Q es el estado de aceptación . Generalmente se representa como un círculo doble. A veces, el estado o los estados de aceptación funcionan como estados " finales " (detención, atrapados). ^{[ 3 ]}

Para un autómata finito determinista (AFD), un autómata finito no determinista (AFN), un autómata finito no determinista generalizado (AFNG) o una máquina de Moore , la entrada se indica en cada arista. Para una máquina de Mealy , la entrada y la salida se indican en cada arista, separadas por una barra inclinada "/": "1/0" indica el cambio de estado al encontrar el símbolo "1", lo que provoca que se genere el símbolo "0". Para una máquina de Moore, la salida del estado se suele escribir dentro del círculo del estado, también separada del designador del estado por una barra inclinada "/". También existen variantes que combinan estas dos notaciones.

Por ejemplo, si un estado tiene varias salidas (p. ej., "a = motor en sentido antihorario = 1, b = luz de precaución inactiva = 0"), el diagrama debe reflejarlo  : p. ej., "q5/1,0" designa el estado q5 con salidas a = 1, b = 0. Este designador se escribirá dentro del círculo del estado.

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