Máquinas de estado finito ¿Qué son? ¿Para qué sirven?

Las máquinas de estados finitos (FSM o Finite-State Machine) son un concepto bien establecido en la informática. Se utilizan en todas partes y en casi todos los sistemas de software que puedas imaginar, ya sea un compilador, un sistema operativo o incluso tu impresora, así como en los autómatas. Estas máquinas de estado son muy utilizadas por las numerosas ventajas que ofrecen respecto a otros métodos de implementación de la misma funcionalidad. Las FSM pueden utilizarse para reducir la complejidad del código separando la lógica en bloques discretos, mejorar la legibilidad del documento organizando el código en subrutinas separadas y facilitar la depuración identificando rutas de ejecución específicas a través del código. En esta entrada del blog aprenderás qué son las máquinas de estado finito y por qué deberías utilizarlas en tu próximo proyecto.

¿Qué es una máquina de estado finito?

Una máquina de estado finito, o FSM, es un modelo de computación que sólo puede estar en uno de un número finito de estados en un momento dado. Como su nombre indica, una FSM es finita en el sentido de que acabará ejecutándose una vez puesta en marcha. El FSM suele estar definido por un conjunto de reglas que describen las transiciones de estado que puede realizar, junto con las entradas que provocan la transición de un estado a otro. Estas entradas también se denominan a veces «eventos». La imagen muestra una máquina de estados finitos en forma de gráfico. Muestra los valores de entrada y las correspondientes transiciones de estado  que se producen. La máquina de estados finitos comienza en el estado S1 y termina en el estado S4, en este caso, después de seguir el camino mostrado.

Por ejemplo, algunos chips basados en electrónica digital tienen dos estados posibles, como sabrás.

¿Por qué se llaman máquinas de estado finito?

Ahora que ya sabes lo que es una FSM, vamos a desgranar un poco el nombre. En informática, una máquina de estados es un tipo de flujo de control que se utiliza a menudo en biología computacional, inteligencia artificial e ingeniería de software. Dado que una FSM sólo puede estar en un estado en un momento dado, puede describirse como una máquina cuyo estado actual es «finito».

¿Cómo se implementa una máquina de estado finito?

La implementación de una máquina de estado finito no es una técnica única, sino una familia de métodos que comparten un principio común. A alto nivel, una máquina de estados finitos puede implementarse de dos maneras (más adelante se hablará de ellas). La primera consiste en utilizar una sentencia if-else. Este método es sencillo de entender e implementar, pero tiene algunos inconvenientes importantes. En primer lugar, el código se vuelve difícil de entender porque todo está agrupado en una gran condición. En segundo lugar, si el estado tiene muchas condiciones, el número de sentencias if puede llegar a ser inmanejable, lo que puede llevar a problemas de legibilidad y depuración. El segundo método para implementar un FSM es utilizar una sentencia switch. La sentencia switch permite escribir una función separada para cada estado y luego ejecutar una de las funciones basada en el estado actual. La ventaja de la sentencia switch es que es más fácil entender el flujo de ejecución a través del código. El lado negativo de esta implementación es que no es muy escalable. Es decir, si el estado tiene muchas condiciones, el número de sentencias switch puede llegar a ser inmanejable, lo que puede llevar a los mismos problemas de legibilidad y depuración.

Ventajas del uso de máquinas de estado finito

Las máquinas de estado finito se utilizan mucho en los sistemas del mundo real, desde una simple aplicación de calculadora hasta una pieza compleja de software como un compilador. A continuación se exponen las ventajas de utilizar FSM frente a otras técnicas:

• Simplicidad: Las máquinas de estado son sencillas de implementar y entender. El flujo de control es claro y no hay estructuras de control complejas, como los bucles, que se interpongan en el camino.
• Extensibilidad: El código es fácil de extender. Todo lo que necesitas hacer es añadir más transiciones con las condiciones adecuadas y no necesitas cambiar el código existente.
• Reutilización: Se puede compartir fácilmente la misma máquina de estado entre múltiples casos de uso. Como la máquina de estado es independiente de los casos de uso, puedes implementarla una vez y utilizarla tantas veces como quieras.
• Capacidad de comprobación: Puedes escribir pruebas unitarias para cada estado y las transiciones entre ellos. Esto facilita la identificación de problemas en el código, especialmente cuando se tiene una máquina de estados grande.

Limitaciones de las máquinas de estados finitos

Ahora que sabes por qué deberías usar FSM, vamos a desgranar algunas de sus limitaciones:

• Complejidad: Una máquina de estado es una herramienta útil para resolver un problema, pero es importante mantenerlas tan simples como sea posible. Si haces la máquina de estado demasiado compleja, acabarás con un código ilegible y difícil de mantener.
• Ordenación de eventos: Un evento puede desencadenar múltiples transiciones. En estos casos, el orden de los eventos puede ser importante. Por ejemplo, en una aplicación de cesta de la compra online, cuando un usuario selecciona un artículo, el sistema puede poner ese artículo en la cesta de la compra, actualizar el subtotal y enviar un correo electrónico al usuario. El orden de estos eventos puede ser importante en determinadas situaciones.

¿Cómo se implementa una máquina de estados finitos?

Para implementar una máquina de estados finitos, primero hay que identificar los estados y las transiciones entre ellos. Esto le ayudará a decidir qué eventos desencadenan las transiciones entre estados. Puedes utilizar una tabla o un diagrama de flujo para visualizar la máquina de estados. Una vez que tengas el diagrama de la máquina de estados listo, puedes implementarlo utilizando la sentencia switch. También puedes utilizar un bucle for si la máquina de estados tiene un número fijo de estados. También puedes utilizar la sentencia if-else si la máquina de estados tiene un número desconocido de estados.

¿Qué es un autómata?

Un autómata es una máquina que funciona por sí misma. Es una máquina que tiene la capacidad de funcionar de forma autónoma. La palabra también se utiliza a veces para referirse a un humanoide artificial, como un robot. El autómata puede funcionar con una amplia gama de tecnologías, como los sistemas mecánicos, hidráulicos, neumáticos, electromecánicos, electromagnéticos o informáticos. El autómata podría funcionar con una secuencia programada de instrucciones, o podría tener capacidades limitadas de autodirección basadas en la inteligencia artificial. Un autómata puede crearse para realizar una tarea específica, o puede diseñarse para ser una novedad divertida. La palabra autómata deriva del griego «automatos», que significa «que actúa por sí mismo» o «autocontrolado».

En resumen:

• Tienen movilidad, es decir, la capacidad de moverse.
• Tienen cierto grado de inteligencia artificial, o la capacidad de ejecutar tareas sin control humano directo.
• Tienen forma de humanos o animales.

La diferencia entre la IA y los autómatas

Aunque tanto la IA (Inteligencia Artificial) como los autómatas tienen que ver con la creación de máquinas sensibles, hay una distinción clave entre ambos. La IA implica la creación de inteligencia artificial mediante una sofisticada programación informática. Los autómatas, en cambio, son máquinas construidas con componentes mecánicos, como engranajes y palancas. La IA utiliza hardware y software informático para simular la inteligencia humana, mientras que los autómatas emplean dispositivos mecánicos como piezas de trabajo. La distinción entre IA y autómatas no es sólo una cuestión de forma. La IA es una tecnología basada en el software y, por lo tanto, puede utilizarse prácticamente en cualquier lugar, desde un smartphone hasta un ordenador. Los autómatas, en cambio, son máquinas físicas y sólo pueden utilizarse en un conjunto limitado de lugares.

La historia de los autómatas

El ser humano ha creado dispositivos mecánicos desde hace miles de años. Por ejemplo, los antiguos griegos construyeron intrincados juguetes mecánicos como regalo para sus hijos. También crearon complejos autómatas para realizar diversas tareas, como accionar las puertas de los templos o hacer girar los teatros. Los autómatas de la Edad Media solían construirse para advertir a la gente del peligro. Por ejemplo, los monjes creaban criaturas mecánicas que daban la alarma cuando se producía un incendio. Los autómatas adquirieron una nueva importancia con la llegada de la industrialización. Aunque las máquinas industriales eran mecánicas, no se consideraban autómatas. Los autómatas adquirieron un nuevo nivel de sofisticación con la llegada de la tecnología informática. Ésta permitió un control aún más sofisticado de los autómatas a través de la programación informática. El auge de la IA aceleró aún más el desarrollo de los autómatas.

Tipos de autómatas

Hay muchos tipos de autómatas, desde los más simples y rudimentarios hasta los más sofisticados. He aquí algunos ejemplos de diferentes tipos de autómatas.

• Muñecos mecánicas: Un muñeco mecánico es un tipo de autómata primitivo en el que una figura humana es controlada por un conjunto de engranajes y un eje giratorio. Aunque estas muñecas se utilizaban a veces como herramientas de enseñanza, también se empleaban como juguetes.
• Juguetes mecánicos: Los juguetes mecánicos están diseñados para parecer reales, pero no están diseñados para ser de tamaño natural como una muñeca. Hay una gran variedad de juguetes que entran en esta categoría, como las cajas de música automáticas, los monos mecánicos y los soldados de juguete de cuerda.
• Robots: Un robot es un autómata mecánico diseñado para un propósito específico. Los robots suelen diferenciarse de otros tipos de autómatas en función del nivel de inteligencia artificial programado en ellos.
• Autómatas: Un autómata es un dispositivo mecánico totalmente autónomo diseñado para realizar una única tarea repetitiva. Un autómata suele funcionar con neumática, hidráulica o electromagnetismo.