Diagrama de estado

Un diagrama de estado para una puerta que sólo se puede abrir y cerrar

Un diagrama de estado es un tipo de diagrama utilizado en informática y campos relacionados para describir el comportamiento de los sistemas. Los diagramas de estado requieren que el sistema descrito esté compuesto por un número finito de estados; a veces, este es realmente el caso, mientras que otras veces es una abstracción razonable. Existen muchas formas de diagramas de estado, que difieren ligeramente y tienen una semántica diferente.

Resumen

Los diagramas de estado se utilizan para dar una descripción abstracta del comportamiento de un sistema. Este comportamiento es analizado y representado por una serie de eventos que pueden ocurrir en uno o más estados posibles. De este modo, "cada diagrama generalmente representa objetos de una sola clase y realiza un seguimiento de los diferentes estados de sus objetos a través del sistema".

Los diagramas de estado se pueden usar para representar gráficamente máquinas de estado finito (también llamadas autómatas finitos). Esto fue presentado 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 posible representación es la tabla de transición de estados.

Gráfico dirigido

Un gráfico dirigido

Una forma clásica de diagrama de estado para un autómata finito (FA) es un gráfico dirigido con los siguientes elementos (Q, Σ, Z, δ, q₀, F):

• Vertices Q: un conjunto finito de estados, normalmente representado por círculos y etiquetado con símbolos únicos de designador o palabras escritas dentro de ellos
• símbolos de entrada: una colección finita de símbolos de entrada o designadores
• símbolos de salida Z: una colección finita de símbolos de salida o designadores

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

• Edges δ: representan transiciones de un estado a otro como causadas por la entrada (identificada por sus símbolos dibujados en los bordes). Un borde generalmente se dibuja como una flecha dirigida desde el estado actual al siguiente estado. Este mapeo describe la transición del estado que va a ocurrir en la entrada de un símbolo particular. Esto está escrito matemáticamente como δ: Q × . → Q, por lo que δ (la función de transición) en la definición de la FA es dada por ambos el par de vértices conectados por un borde y el símbolo en un borde en un diagrama que representa esta FA. Tema δ(q, a) = p en la definición de la FA significa que desde el estado llamado q bajo símbolo de entrada a, la transición al estado p ocurre en esta máquina. En el diagrama que representa esta FA, esto está representado por un borde etiquetado por a señalando desde el vértice etiquetado por q al vertex etiquetado por p.
• Estado de inicio q₀: (no se muestra en los ejemplos siguientes). El estado de inicio q₀ ANTE Q generalmente está representado por una flecha sin origen apuntando al estado. En textos antiguos, el estado inicial no se muestra y debe ser inferido del texto.
• Estado(s) aceptado(s) F: Si se utiliza, por ejemplo para aceptar automata, F Iberia Q es el estado de aceptación. Por lo general se dibuja como un círculo doble. A veces el estado(s) aceptado funciona como "Festados inal" (medio, atrapado).

Para un autómata finito determinista (DFA), un autómata finito no determinista (NFA), un autómata finito no determinista generalizado (GNFA) o una máquina de Moore, la entrada se indica en cada borde. Para una máquina Mealy, la entrada y la salida se indican en cada borde, separadas por una barra inclinada "/": "1/0" denota el cambio de estado al encontrar el símbolo "1" causando el símbolo "0" para ser salida. Para una máquina de Moore, la salida del estado generalmente se escribe dentro del círculo del estado, también separada del designador del estado con una barra inclinada '/'. También hay variantes que combinan estas dos notaciones.

Por ejemplo, si un estado tiene varias salidas (por ejemplo, "a= motor en sentido contrario a las agujas del reloj=1, b= luz de precaución inactiva=0"), el diagrama debería reflejar esto: p. "q5/1,0" designa el estado q5 con salidas a=1, b=0. Este designador se escribirá dentro del círculo del estado.

Ejemplo: máquina DFA, NFA, GNFA o Moore

S₁ y S₂ son estados y S ₁ es un estado de aceptación o un estado final. Cada borde está etiquetado con la entrada. Este ejemplo muestra un aceptador de números binarios que contienen un número par de ceros.

Ejemplo: Máquina harinosa

S₀, S₁ y S₂ son estados. Cada borde está etiquetado con "j / k" donde j es la entrada y k es la salida.

Gráfico de estado de Harel

Diagrama que muestra cómo los Statecharts de Harel contribuyeron a métodos y notación orientados a objetos

Los diagramas de estado de Harel, inventados por el científico informático David Harel, están ganando un uso generalizado desde que una variante se convirtió en parte del lenguaje de modelado unificado (UML). El tipo de diagrama permite el modelado de superestados, regiones ortogonales y actividades como parte de un estado.

Los diagramas de estado clásicos requieren la creación de nodos distintos para cada combinación válida de parámetros que definen el estado. Esto puede conducir a una gran cantidad de nodos y transiciones entre nodos para todos los sistemas, excepto los más simples (explosión de estados y transiciones). Esta complejidad reduce la legibilidad del diagrama de estado. Con los diagramas de estado de Harel, es posible modelar múltiples diagramas de estado interfuncionales dentro del diagrama de estado. Cada una de estas máquinas de estado de funciones cruzadas puede realizar una transición interna sin afectar a las otras máquinas de estado en el diagrama de estado. El estado actual de cada máquina de estado multifuncional en el diagrama de estado define el estado del sistema. El diagrama de estado de Harel es equivalente a un diagrama de estado, pero mejora la legibilidad del diagrama resultante.

Semántica alternativa

Hay otros conjuntos de semántica disponibles para representar diagramas de estado. Por ejemplo, existen herramientas para modelar y diseñar la lógica de los controladores integrados. Estos diagramas, al igual que las máquinas de estado originales de Harel, admiten estados anidados jerárquicamente, regiones ortogonales, acciones de estado y acciones de transición.

Diagramas de estado y diagramas de flujo

Los recién llegados al formalismo de la máquina de estados a menudo confunden diagramas de estado con diagramas de flujo. La siguiente figura muestra una comparación de un diagrama de estado con un diagrama de flujo. Una máquina de estado (panel (a)) realiza acciones en respuesta a eventos explícitos. Por el contrario, el diagrama de flujo (panel (b)) no necesita eventos explícitos sino transiciones de nodo a nodo en su gráfico automáticamente al finalizar las actividades.

Los nodos de los diagramas de flujo son bordes en el gráfico de estados inducido. La razón es que cada nodo en un diagrama de flujo representa un comando de programa. Un comando de programa es una acción a ejecutar. Por lo tanto, no es un estado, pero cuando se aplica al estado del programa, da como resultado una transición a otro estado.

Con más detalle, la lista de código fuente representa un gráfico de programa. Ejecutar el gráfico de programa (analizar e interpretar) da como resultado un gráfico de estado. Entonces, cada gráfico de programa induce un gráfico de estado. La conversión del gráfico de programa a su gráfico de estado asociado se denomina "desdoblamiento" del gráfico del programa.

El gráfico del programa es una secuencia de comandos. Si no existen variables, entonces el estado consiste solo en el contador del programa, que realiza un seguimiento de en qué parte del programa estamos durante la ejecución (cuál es el siguiente comando que se aplicará).

En este caso, antes de ejecutar un comando, el contador del programa está en alguna posición (estado antes de ejecutar el comando). Ejecutar el comando mueve el contador del programa al siguiente comando. Dado que el contador del programa es el estado completo, se deduce que la ejecución del comando cambió el estado. Entonces el comando en sí corresponde a una transición entre los dos estados.

Ahora considere el caso completo, cuando las variables existen y se ven afectadas por los comandos del programa que se ejecutan. Luego, entre diferentes ubicaciones del contador del programa, no solo cambia el contador del programa, sino que las variables también pueden cambiar los valores, debido a los comandos ejecutados. En consecuencia, incluso si revisamos algún comando del programa (por ejemplo, en un bucle), esto no implica que el programa esté en el mismo estado.

En el caso anterior, el programa estaría en el mismo estado, porque todo el estado es solo el contador del programa, por lo que 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, entonces si estas cambian de valor, podemos estar en la misma ubicación del programa con diferentes valores de variable, es decir, en un estado diferente en el espacio de estado del programa. El término "desdoblamiento" se origina a partir de esta multiplicación de ubicaciones al producir el gráfico de estado a partir del gráfico de programa.

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

Un ejemplo representativo es un bucle do que incrementa algún contador hasta que se desborda y vuelve a ser 0. Aunque el bucle do ejecuta el mismo comando de incremento iterativamente, por lo que el gráfico del programa ejecuta un ciclo, en su espacio de estado no hay un ciclo, sino una línea. Esto se debe a que el estado es la ubicación del programa (aquí, el ciclo) combinado con el valor del contador, que aumenta estrictamente (hasta el desbordamiento), por lo que se visitan diferentes estados en secuencia, hasta el desbordamiento. Después del desbordamiento, el contador vuelve a ser 0, por lo que se vuelve a visitar el estado inicial en el espacio de estado, cerrando un ciclo en el espacio de estado (suponiendo que el contador se inicializó a 0).

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.

Puede comparar un diagrama de flujo con una línea de ensamblaje en la fabricación porque el diagrama de flujo describe la progresión de alguna tarea de principio a fin (por ejemplo, transformar la entrada del código fuente en la salida del código objeto por parte de un compilador). Una máquina de estado generalmente no tiene noción de tal progresión. La máquina de estado de la puerta que se muestra en la parte superior de este artículo, por ejemplo, no se encuentra en una etapa más avanzada cuando está en el modo "cerrado" estado, en comparación con estar en el estado "abierto" estado; simplemente reacciona de manera diferente a los eventos de apertura/cierre. Un estado en una máquina de estado es una forma eficiente de especificar un comportamiento particular, en lugar de una etapa de procesamiento.

Otras extensiones

Una extensión interesante es permitir que los arcos fluyan desde cualquier número de estados a cualquier número de estados. Esto solo tiene sentido si se permite que el sistema esté en varios estados a la vez, lo que implica que un estado individual solo describe una condición u otro aspecto parcial del estado global general. 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 estado de Harel. Esta extensión es compatible con el desarrollo de software que se basa tanto en eventos como en flujos de trabajo.