Máquinas de estados finitos

Una descripción general rápida de qué son las máquinas de estados, con ejemplos simples

Estos días se habla mucho de máquinas de estados finitos en el mundo de JavaScript.

Existe una biblioteca popular llamada XState , con más de 11 000 estrellas en GitHub, con la que me topé recientemente y sigo leyendo sobre ella en Twitter y otros lugares. Es un proyecto muy interesante.

Conocí las máquinas de estados finitos y los autómatas en la escuela secundaria, hace 20 años, y luego los volví a encontrar 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 estados secuenciales, circuitos aritméticos, VHDL y más.

Me pareció bastante sorprendente el tema de las máquinas de estados finitos aplicadas a la ingeniería frontend, y volví a mis viejos libros para ver si podía encontrar una buena explicación de ellas.

Encontré mucha información y, por supuesto, al ser libros de texto, las cosas se complican más de lo necesario (en mi humilde opinión). Me gusta simplificar las cosas y decidí escribir una pequeña explicación para seres humanos normales, nada teórico ni nada hecho para aprobar un examen. Cosas que se puedan aplicar al mundo real.

Máquinas de estados

Antes de analizar qué es una máquina de estados finitos, quiero presentar primero qué es una máquina de estados.

El mundo está lleno de máquinas de estados. Puedes verlas en todas partes, pero quizás no las hayas considerado como tales. Después de leer este tutorial, estoy seguro de que señalarás objetos en el mundo real y les dirás a tus amigos “eso es una máquina de estados ” (dependiendo del nivel de frikis 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. Normalmente, puede ser:

• tiene la luz verde encendida y las otras 2 luces apagadas
• tiene la luz roja encendida y las otras 2 luces apagadas
• como la luz amarilla encendida y las otras 2 luces apagadas

(Algunos semáforos son ligeramente diferentes, pero no nos interesan para este ejemplo)

En la terminología de máquinas de estados, el encendido o apagado de las luces se denomina salida .

Cada uno de esos tres escenarios se denomina estado . El semáforo de tráfico cambiará de estado cuando reciba una entrada, normalmente un temporizador fijo que decide durante cuánto tiempo los semáforos deben estar en verde, amarillo y rojo.

En este caso, el temporizador es la entrada del sistema. Algunos semáforos tienen un botón que el peatón puede presionar para que los autos vean la luz roja, y esa 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 estados finitos

Se dice que nuestra máquina de estados de semáforos 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, ¿y los semáforos? Es algo sencillo y tiene tres estados, como ya hemos dicho.

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 autónomo
• Un ascensor

Pero sigamos con nuestro ejemplo del semáforo, que es muy sencillo y podemos razonar sobre él fácilmente.

Modelado de una máquina de estados

Por supuesto, los semáforos no existen de forma aislada. Se trata de otra máquina de estados finitos, que contiene varias máquinas de estados finitos diferentes para cada dispositivo de semáforo instalado en cada lado de cada calle de una intersección, que funcionan en sincronía.

No lo pienses ahora. Centrémonos en un único semáforo de tráfico.

Como dijimos más arriba, tenemos 3 estados, que podemos llamar verde, rojo, amarillo.

Tenemos un estado inicial. Digamos que nuestros semáforos se ponen en marcha, cuando los reiniciamos, en ese greenestado.

Tenemos un temporizador que, después de 50 segundos de estado verde, mueve el semáforo al yellowestado. Tenemos 8 segundos de yellowestado, luego nos movemos al redestado y nos quedamos allí 32 segundos, porque esa carretera 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 se detiene la electricidad y el semáforo se reinicia cuando vuelve a recibir energía.

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 actualmente la máquina, cuál es la entrada que recibe, cuál es el siguiente estado y la salida :

En nuestro caso simple, dado cualquier estado de la máquina, solo tenemos un estado lógico al cual ir, por lo que la tabla y el gráfico que hice son muy, muy simples.

Pero cuando el sistema comienza a volverse más complejo, es muy útil tener estos diagramas y análisis preparados porque puedes razonar sobre tu aplicación mucho más fácilmente que si simplemente mantienes todo en tu cabeza.

Una máquina de estados finitos con transiciones de estados más complejas

El ejemplo anterior es muy simple. Ahora, modelemos otra máquina de estados finitos.

Nuestro escenario en el mundo real es este: tenemos una casa, con una puerta, 2 botones y 3 luces.

En el estado predeterminado, todas las luces están apagadas.

Al entrar a la casa, puedes presionar uno de los 2 pulsadores que tiene, p1o p2. Al presionar cualquiera de esos botones, la l1luz se enciende.

Imagina que esta es la luz de la entrada y que puedes quitarte la chaqueta. Una vez que hayas terminado, decides a qué habitación quieres ir (cocina o dormitorio, por ejemplo).

Si presionas el botón p1, l1se apaga y l2se enciende. En cambio si presionas el botón p2, l1se apaga y l3se enciende.

Presionando otra vez cualquiera de los 2 botones, p1o p2, la luz que esté encendida en ese momento se apagará y volveremos al estado inicial del sistema.

Esta máquina de estados finitos es un poco más compleja que la primera, porque esta vez podemos tener múltiples rutas dependiendo de la entrada.

Vamos a modelar esto.

Básicamente tenemos 4 estados:

• No hay luces encendidas
• l1encendido
• l2encendido
• l3encendido

Tenemos 2 entradas:

• p1
• p2

Si partimos del estado inicial y tratamos de modelar todo lo que puede suceder dependiendo de cómo se activen las entradas a lo largo del tiempo, terminamos con:

Lo cual se puede resumir utilizando esta tabla:

Es una explicación corta y sencilla, pero quizá haga que las cosas entiendan.

Tal vez te puede interesar:

1. Introducción a React
2. Agregar evento de clic a los elementos DOM devueltos desde querySelectorAll
3. Cómo cambiar el valor de un nodo DOM
4. Cómo comprobar si un elemento DOM tiene una clase

Máquinas de estados finitos

Máquinas de estadosMáquinas de estados finitosModelado de una máquina de estadosUna máquina de estados finitos con transiciones de estados más complejas

programar

es

2025-01-03

Si crees que alguno de los contenidos (texto, imagenes o multimedia) en esta página infringe tus derechos relativos a propiedad intelectual, marcas registradas o cualquier otro de tus derechos, por favor ponte en contacto con nosotros en el mail [email protected] y retiraremos este contenido inmediatamente