Explicación de la máquina de estados finitos

La máquina de estados finitos (FSM) es un patrón de diseño de software en el que un modelo dado pasa a otros estados de comportamiento a través de una entrada externa.

Comprensión de la máquina de estados finitos

Un FSM se define por sus estados , su estado inicial y las transiciones .

El poder de FSM proviene de la capacidad de definir claramente diferentes comportamientos en diferentes condiciones. Por lo general, FSM se usa con scripts de comportamiento en bucle que evalúan constantemente la situación actual en un bucle o con eventos.

Para ayudar a formar una imagen de cómo se podría aplicar esto, se utilizará una máquina de café como ejemplo de una máquina de estados finitos. También cubriremos un diagrama de estado para visualizar el FSM y proporcionar ejemplos de codificación.

Diagrama de estado

Diagrama de máquina de estado finito de la máquina de café

Este diagrama muestra tres estados posibles para la máquina de café:

  • Abierto
  • ReadyToBuy
  • Apagado

Las líneas entre estos estados muestran qué transiciones son posibles entre estados y en qué dirección. Estas transiciones tienen condiciones para cuando el FSM necesita cambiar entre estados.

  • StartUpMachine Desde el estado PoweredOff hasta el estado Abierto, la máquina debe iniciarse. En este caso, esto se hace manualmente.
  • depósito> = costo del café El FSM evalúa la cantidad de efectivo depositado ya sea en un ciclo o cuando la cantidad cambia (recomendado en este caso) Si deposita suficiente efectivo en la máquina de café, el FSM pasará de 'Abierto' a 'ReadyToBuy '.
  • ShutdownMachine La máquina pasará automáticamente de Open a PoweredOff a través del método ShutDownMachine si se cumple la condición 'no quedan más cafés'.
  • DispenseCoffee En el estado ReadyToBuy, el usuario puede comprar un café, después de lo cual será preparado y dispensado. La condición es cuando se activa el evento BuyCoffee (! Enlace al patrón del observador!). (no se muestra en el diagrama)
  • CancelCoffee Si el usuario opta por cancelar, la máquina pasará de ReadyToBuy a Open.
  • ShutDownMachine La máquina pasará al estado PoweredOff

Estados

En cada estado hay un comportamiento definido que solo se ejecutará cuando el objeto esté en ese estado. Por ejemplo, durante PoweredOff, la máquina de café no preparará café antes de encenderse, durante el estado Abierto esperará hasta que haya suficiente dinero en efectivo insertado, hasta que se dé el comando de apagado o hasta que se acabe el café. Durante este estado Abierto, puede realizar rutinas como la limpieza que no sucederán en otros estados.

Estado inicial

Cada FSM tiene un estado inicial, esto significa en qué estado comienza cuando se crea y debe definirse cuando se construye o instancia. Por supuesto, es posible cambiar de estado directamente si se cumplen las condiciones.

Transiciones

Cada estado evalúa constantemente si debe pasar a otro estado o pasará a otro estado en función de un evento desencadenado.

DFA y NFA

Hay dos tipos de autómatas finitos, deterministas (DFA) y no deterministas (NFA). Ambos aceptan lenguajes regulares y operan más o menos de la misma manera descrita anteriormente, pero con algunas diferencias.

Un DFA acepta o rechaza una cadena de símbolos y solo produce un cálculo o autómata único para cada cadena de entrada. Determinista se refiere a la singularidad del cálculo. Una máquina de estados finitos se denomina DFA si obedece las siguientes reglas:

  1. Cada una de sus transiciones está determinada de forma única por su estado de origen y símbolo de entrada
  2. Es necesario leer un símbolo de entrada para cada transición de estado.

Una NFA no necesita obedecer estas restricciones, lo que significa que cada DFA también es una NFA. Y dado que ambos solo reconocen idiomas regulares, cada NFA se puede convertir en un DFA equivalente utilizando el algoritmo de construcción de powerset.

Entonces, ¿qué tipo de reglas podemos esperar encontrar en las NFA pero no en las DFA?

  1. Un NFA puede tener una transición de cadena vacía (generalmente denotado por un épsilon). Lo que significa que cuando se encuentra en un cierto estado con un épsilon para una regla de transición, la máquina puede pasar al siguiente estado sin leer un símbolo de entrada.
  2. En un NFA, cada par de estado y símbolo de transición puede tener varios estados de destino en lugar de los destinos únicos de los pares en los DFA
  3. Cada par de estado y símbolo de transición produce una "rama" de cálculo para cada uno de sus posibles destinos creando una especie de sistema multiproceso.
  4. Un DFA rechazará la cadena de entrada si aterriza en cualquier estado que no sea el estado de aceptación. En una NFA, solo necesitamos una 'rama' para aterrizar en un estado de aceptación para aceptar la cadena.

Si desea obtener más información, aquí hay una excelente guía detallada sobre máquinas de estado.