Máquinas de estados finitos: la clave oculta de la Inteligencia artificial

Para el diseño de sistemas inteligentes, como los utilizados en los ordenadores actuales, se necesitan métodos y análisis como los de las conocidas como máquinas de estados finitos (MEF) o en inglés Finite State Machine (FSM). ¿Sabes qué es? Te lo explicamos…

¿Qué son las Máquinas de Estado Finito?

Una FSM es un modelo de cálculo abstracto que consta de una serie de estados, que representan las distintas configuraciones o estados del sistema, además de una serie de transiciones o conexiones entre estados que se activan en base a las entradas o condiciones específicas del sistema. Por supuesto, como cualquier sistema automático, tiene sus entradas y sus salidas. Todo ello se puede apreciar en la imagen anterior de un diagrama ejemplo.

Dentro de las FSM, se puede diferenciar entre:

• De Mealy: en este tipo de máquina de estado finito, las salidas dependen tanto del estado actual como de las entradas.
• De Moore: en este otro caso las salidas dependen únicamente del estado actual, sin importar la entrada.

Por ejemplo, imagina un controlador de unidad de disco de un sistema operativo. En este caso puede ser diseñado mediante una FSM para gestionar las operaciones acceso a la unidad de memoria, es decir, para la lectura o escritura. El sistema realiza transiciones entre diferentes estados según las instrucciones y condiciones detectadas en cada momento. Los estados en este caso serían:

• IDLE (Inactivo): el controlador está esperando una solicitud.
• READ (Lectura): el controlador está leyendo datos del disco.
• WRITE (Escritura): el controlador está escribiendo datos en el disco.
• ERROR: se detecta un fallo en la operación.

El esquema sería el siguiente:

(IDLE) –> (READ) –> (IDLE)
|                      |
V                    V
(WRITE) –> (ERROR)

Y la tabla explicando esta FSM de forma sencilla sería:

Estado Actual	Entrada	Nuevo Estado	Descripción
IDLE	Solicitud de Lectura	READ	Se inicia una operación de lectura.
IDLE	Solicitud de Escritura	WRITE	Se inicia una operación de escritura.
READ	Operación Exitosa	IDLE	Se completa la lectura y el controlador vuelve a IDLE.
READ	Fallo Detectado	ERROR	Ocurre un fallo durante la lectura.
WRITE	Operación Exitosa	IDLE	Se completa la escritura y el controlador vuelve a IDLE.
WRITE	Fallo Detectado	ERROR	Ocurre un fallo durante la escritura.
ERROR	Reinicio del Sistema	IDLE	Se resuelve el error y el controlador vuelve a IDLE.

Historia de las Máquinas de Estado Finito

El concepto de FSM tiene sus raíces en la teoría de autómatas, una rama de las matemáticas formales que estudia sistemas discretos. Fue formalizado en la década de 1940 y 1950 como parte del desarrollo de la teoría de la computación. Algunos hitos importantes incluyen:

• 1936: Alan Turing introdujo el concepto de Máquina de Turing, un modelo más general que las FSM, pero cuyos principios están relacionados.
• 1943: un poco más tarde, Warren McCulloch y Walter Pitts propusieron modelos matemáticos de redes neuronales basados en autómatas finitos, precursores de las FSM.
• 1956: Noam Chomsky y Stephen Kleene desarrollaron teorías de lenguajes regulares y autómatas finitos, estableciendo una relación entre estos sistemas y la gramática formal.

Con el auge de la electrónica digital y la computación en las décadas de 1950 y 1960, las FSM comenzaron a implementarse en hardware para modelar circuitos lógicos secuenciales. Primeramente se utilizaron para controladores de hardware, lenguajes de programación y compiladores entre los años 60 y 70, para más tarde, a partir de los años 80s usarse para modelar software y hardware de una forma más importante.

Aplicaciones de las FSM

Entre las aplicaciones de las máquinas de estado finito, tenemos:

• Controladores secuenciales: son fundamentales en circuitos digitales para diseñar controladores que operan dispositivos microprocesadores y sistemas de memoria.

Te puede interesar conocer los mejores procesadores del mercado

• Automatización de protocolos: Implementación de protocolos de comunicación, como UART y SPI, donde cada etapa de transmisión o recepción es un estado.
• Compiladores: para analizar cadenas de texto y verificar que cumplen con una gramática determinada.
• Sistemas de control: desde juegos hasta sistemas operativos, para controlar toda la lógica secuencial.
• Robótica y automatización industrial: se emplean para diseñar sistemas de control en robots que cambian entre diferentes comportamientos, como moverse, evitar obstáculos y cargar energía.
• Procesamiento de Lenguaje Natural (PLN): para reconocer patrones y análisis de léxico automatizado, modelos simples gramaticales, y lenguajes regulares.

También te recomiendo leer sobre qué es una NPU

Los actuales sistemas de IA están muy estrechamente relacionados con FSM, por lo que son métodos a los que tener muy en cuenta…

Deja tus comentarios con dudas o sugerencias…