Se habla mucho de las Máquinas de Estado Finito estos días en la tierra de JavaScript.
Hay una biblioteca popular llamada XState, con más de 11000 estrellas en GitHub, con la que me encuentro últimamente, y sigo leyendo sobre ella en Twitter y otros lugares. Es un proyecto muy chulo.
La primera vez que conocí las máquinas de estado finito y los autómatas fue en el instituto, hace 20 años, y luego los volví a conocer en mi curso de Diseño Digital en la Universidad.
Este curso de Diseño Digital trataba sobre codificación de información, álgebra booleana, redes combinatorias, circuitos secuenciales, máquinas de estado secuenciales, circuitos aritméticos, VHDL, y más.
El tema de las Máquinas de Estado Finito aplicadas a la Ingeniería Frontend me pareció bastante sorprendente, y volví a mis viejos libros para ver si encontraba una buena explicación de las mismas.
Encontré mucha información, y por supuesto al ser libros de texto las cosas se hacen más complejas de lo necesario (IMHO). Me gusta simplificar las cosas, y decidí escribir una pequeña explicación para seres humanos normales, no teórica ni nada hecho para pasar un examen. Cosas que puedas aplicar al mundo real.
Máquinas de Estado
Antes de ver qué es una Máquina de Estado Finita, quiero introducir primero qué es una Máquina de Estado.
El mundo está lleno de máquinas de estado. Las puedes ver por todas partes, pero quizás no pensabas en ellas como tal. Después de leer este tutorial, estoy seguro de que señalarás objetos en el mundo real diciendo a tus amigos «eso es una máquina de estado» (dependiendo del nivel de frikismo de tus amigos).
El ejemplo más popular y comúnmente encontrado son los semáforos.
En cualquier momento, un semáforo de tráfico tiene un estado definido. Típicamente, o bien:
- tiene la luz verde encendida, y las otras 2 luces apagadas
- tiene la luz roja encendida, y las otras 2 luces apagadas
- tiene la luz amarilla encendida y las otras 2 luces apagadas
(Algunos semáforos son ligeramente diferentes, pero no nos importa por el bien de este ejemplo)
En la terminología de las Máquinas de Estado, que las luces estén encendidas o apagadas se llama salida.
Cada uno de esos 3 escenarios se llama estado. El semáforo de tráfico cambiará de estado cuando reciba una entrada, normalmente sólo un temporizador fijo que decide cuánto tiempo deben estar los semáforos en verde, amarillo y rojo.
El temporizador en este caso es la entrada del sistema. Algunos semáforos tienen un botón que el peatón puede pulsar para hacer que el rojo se muestre a los coches, y eso sería otra entrada.
En una máquina de estados, el estado sólo puede cambiar (y tenemos una transición) en respuesta a una entrada.
Máquinas de estado finitas
Nuestra máquina de estado del semáforo se dice que es finita porque tenemos un número finito de estados.
Algunos sistemas pueden tener un número infinito de estados.
Como el modelo del ecosistema mundial, o la vida de un insecto. No podemos definirlo en un número finito de estados.
¿Pero los semáforos? Eso es algo sencillo, y tiene 3 estados, como dijimos arriba.
Hay muchos más ejemplos de máquinas de estados finitos que podríamos utilizar:
- una máquina expendedora
- un torniquete de entrada al metro
- un sistema de calefacción
- un sistema de metro automatizado
- un sistema de coche autoconducido
- un ascensor
- sin luces encendidas
-
l1encendidas -
l2encendida -
l3encendida p1p2- Máquinas de Estado Finito
- El Sistema Numérico Decimal
- El Sistema Numérico Binario
- Conversión de Números de Decimal a Binario
- Lista de caracteres ASCII imprimibles
- Lista de caracteres ASCII no imprimibles
- Lista de caracteres ASCII no imprimibles
- Cómo conectarse a una Raspberry Pi utilizando un Mac
- Cómo asegurarse de que la Raspberry Pi tiene siempre la misma dirección IP
- Una muy breve introducción a COBOL
Pero quedémonos con nuestro ejemplo de los semáforos, que es muy sencillo y podemos razonar sobre él fácilmente.
Modelando una máquina de estados
Por supuesto, los semáforos no existen de forma aislada. Esa es otra máquina de estados finitos, que contiene múltiples máquinas de estados finitos diferentes para cada dispositivo de semáforo instalado para cada lado de cada carretera de una intersección, que funcionan de forma sincronizada.
No pienses en ello ahora. Vamos a centrarnos en 1 solo semáforo de tráfico.
Como hemos dicho anteriormente, tenemos 3 estados, que pueden llamarse verde, rojo, amarillo.
Tenemos un estado inicial. Digamos que nuestro semáforo comienza, cuando lo reseteamos, en el estado green.
Tenemos un temporizador que tras 50 segundos de estado verde, mueve el semáforo al estado yellow. Tenemos 8 segundos de estado yellow, luego pasamos al estado red, y nos quedamos ahí 32 segundos, porque esa vía es secundaria y merece menos tiempo de verde. Después de esto, el semáforo vuelve al estado verde y el ciclo continúa indefinidamente, hasta que la electricidad se detiene y el semáforo se reinicia cuando recibe la energía de nuevo.
En total, tenemos un ciclo de 90 segundos.
Así es como podemos modelarlo:
También podemos modelarlo con una tabla de transición de estados, que muestra el estado en el que se encuentra la máquina actualmente, cuál es la entrada que recibe, cuál es el siguiente estado y la salida:
| Estado | Entrada | Siguiente estado | Salida |
|---|---|---|---|
| Verde | Timer 50s | Amarillo | Luz verde encendida, otras apagadas |
| Amarillo | Timer 8s | Rojo | Luz amarilla encendida, otras apagadas |
| Rojo | Temporizador 32s | Luz verde encendida, otras apagadas | Luz roja encendida, otras apagadas |
En nuestro caso sencillo, dado cualquier estado de la máquina sólo tenemos un estado lógico al que ir, así que la tabla y el gráfico que he hecho son muy, muy sencillos.
Pero cuando tu sistema empieza a ser más complejo, es muy útil tener este tipo de diagramas y análisis porque puedes razonar sobre tu aplicación mucho más fácilmente que simplemente guardando todo en tu cabeza.
Una Máquina de Estado Finito con Transiciones de Estado más complejas
El ejemplo anterior es muy sencillo. Vamos a modelar ahora otra Máquina de Estado Finito.
Nuestro escenario del mundo real es este: tenemos una casa, con una puerta, 2 botones y 3 luces.
En el estado por defecto las luces están todas apagadas.
Cuando entras en la casa, puedes pulsar uno de los 2 pulsadores que tienes, p1 o p2. Cuando pulsas cualquiera de esos botones, se enciende la luz l1.
Imagina que es la luz de entrada, y que puedes quitarte la chaqueta. Una vez que lo haces, decides a qué habitación quieres entrar (cocina o dormitorio, por ejemplo).
Si pulsas el botón p1l1 se apaga y l2 se enciende. En cambio si pulsas el botón p2l1 se apaga y l3 se enciende.
Pulsando otra vez cualquiera de los 2 botones, p1 o p2, la luz que está actualmente encendida se apagará, y volveremos al estado inicial del sistema.
Esta máquina de estados finitos es algo más compleja que la primera, ya que esta vez podemos tener múltiples rutas en función de la entrada.
Modelemos esto.
Básicamente tenemos 4 estados:
Tenemos 2 entradas:
Si partimos del estado inicial, y tratamos de modelar todo lo que puede ocurrir dependiendo de cómo se disparen las entradas a lo largo del tiempo, acabamos con:
Que se puede resumir mediante esta tabla:
| Estado | Entrada | Siguiente estado |
|---|---|---|
| sin luces encendidas | p1 pulsado |
l1 encendido |
| sin luces encendidas | p2 pulsado |
|
l2 encendido |
l1 encendido |
l3 encendida |
l2 encendida |
sin luces encendidas | |
l2 encendidas |
sin luces encendidas | |
l3 encendida |
sin luces encendidas | |
l3 encendida |
sin luces encendidas |
Es una explicación corta y sencilla, pero tal vez haga que las cosas «hagan clic».
Más tutoriales de informática:
.lista de caracteres ASCII imprimibles