Introducción a las Máquinas de Estado Finito

Escrito por Raúl Alvarez.

Sistema Embebido Si ya haz realizado proyectos con microcontroladores en el pasado, pero nunca haz usado Máquinas de Estado Finito y tampoco estás seguro de lo que son, posiblemente te falta dar el siguiente "salto' que te acerque a un estilo más profesional en la programación de microcontroladores y/o microprocesadores a través del uso de herramientas y paradigmas más sofisticados como, en este caso, las Máquinas de Estado Finito.

No es de extrañar que muchos desarrolladores profesionales de sistemas embebidos de talla mundial, no solamente usen regularmente este estilo de programación, sino que recomienden enfáticamente su uso en cualquier proyecto que se preste a ello (la mayoría de los sistemas reactivos de pequeña y mediana escala, por ejemplo). Lo que sí sorprende es que muchos estudiantes y egresados de la carrera de electrónica u otras carreras afines al diseño embebido no han aprendido a usar este patrón de programación en el desarrollo de sistemas embebidos. En este artículo le damos un vistazo introductorio a este tema.

¿Que es una Máquina de Estado Finito?

Una Máquina de Estado Finito (Finite State Machine), llamada también Autómata Finito es una abstracción computacional que describe el comportamiento de un sistema reactivo mediante un número determinado de Estados y un número determinado de Transiciones entre dicho Estados.

Las Transiciones de un estado a otro se generan en respuesta a eventos de entrada externos e internos; a su vez estas transiciones y/o subsecuentes estados pueden generar otros eventos de salida. Esta dependencia de las acciones (respuesta) del sistema a los eventos de entrada hace que las Máquinas de Estado Finito (MEF) sean una herramienta adecuada para el diseño de Sistemas Reactivos y la Programación Conducida por Eventos (Event Driven Programming), cual es el caso de la mayoría de los sistemas embebidos basados en microcontroladores o microprocesadores.

Las MEF se describen gráficamente mediante los llamados Diagramas de Estado Finito (DEF), llamados también Diagramas de Transición de Estados.

Sistemas Reactivos
Un Sistema Reactivo es aquel que interactúa constantemente con su medio ambiente, tiene la característica de ser conducido por eventos (event driven), la respuesta de tiempo es crítica y una vez que el sistema se activa permanece en ese estado de manera indefinida. En estos sistemas los eventos llegan en tiempos impredecibles y el sistema debe tener la capacidad de responder de manera inmediata, en el orden de los milisegundos o microsegundos, sobre todo en sistemas donde la seguridad es crítica (ejemplo: un piloto automático en un avión o una máquina para soporte de vida en un hospital).

La gran mayoría de los sistemas embebidos (en base a microcontroladores o microprocesadores) corresponden a esta categoría, debido a que estos sistemas están típicamente conectados a varios tipos de sensores y transductores de entrada encargados de captar los estímulos del medio ambiente (temperatura, presión, luz, magnetismo, fuerza / peso, etc.), procesar dicha información y generar una respuesta del sistema hacia el medio ambiente a través de transductores de salida y actuadores.

Sistemas Transformacionales
A diferencia de los Sistemas Reactivos un Sistema Transformacional es aquel que recibe cierta información de entrada, realiza una cierta cantidad de cómputo, produce cierta información de salida y luego termina. No muchos sistemas embebidos caen en esta categoría; ejemplo más típicos son las aplicaciones para PC, como por ejemplo: Un procesador de texto.

Diagrama de Estado Finito o Diagrama de Transición de Estados

Un Diagrama de Estado Finito es un gráfico que representa los diferentes estados de una MEF y todas las transiciones posibles entre los estados.

Como ejemplo, consideremos un muy simplificado sistema de control de un ascensor:

Máquina de Estado Finito Transductora

Estados: El sistema está formado por tres estados: DETENIDO, YENDO_ARRIBA y YENDO_ABAJO. Los diferentes estados se los representa mediante bloques cuadrados (como en este caso) o círculos.

Transiciones: Las transiciones se las representa mediante flechas que indican la dirección de transición de un estado a otro.

Eventos: Los eventos para el sistema en este ejemplo son los siguientes:

seleccion_piso: Es un evento externo que se genera toda vez que un usuario selecciona un piso o llama al ascensor desde otro piso.
arribo_nuevo_piso: Es un evento interno que se genera cada vez que los sensores detectan que se ha arribado al nuevo piso seleccionado por el usuario.

Los eventos se anotan en el gráfico por encima de las flechas de transición.

Condiciones de Transición: Dos transiciones en este sistema de ejemplo tienen asociadas sus respectivas Condiciones de Transición. No todas las transiciones poseen Condiciones de Transición.

piso_nuevo > piso_actual: Es la condición necesaria para que se produzca una transición del estado DETENIDO al estado YENDO_ARRIBA.
piso_nuevo < piso_actual: Es la condición necesaria para que se produzca una transición del estado DETENIDO al estado YENDO_ABAJO.

Las Condiciones de Transición se anotan por debajo de las flechas de transición.

Una pseudo transición inicial del punto rojo al estado DETENIDO identifica a este último como el estado inicial de la MEF.

Codificación en Lenguaje C

El sistema de control del ascensor se puede codificar en Lenguaje C de la siguiente manera:

/* Ejemplo de Máquina de Estado Finito para un ascensor simplificado */
enum eEstados {    // Los estados se la MEF se definen en una enumeracion
     DETENIDO,
     YENDO_ARRIBA,
     YENDO_ABAJO
 } estado;

int piso_nuevo, piso_actual;
main() {
   estado = DETENIDO;    // La MEF se inicializa en estado DETENIDO
   while (TRUE) {
     switch (estado) {
       case DETENIDO:{    // 
         // Verificar si se ha seleccionado un nuevo piso:
         piso_nuevo = seleccion_piso();    
         if (piso_nuevo > piso_actual)
           estado = YENDO_ARRIBA;
         else if (piso_nuevo < piso_actual)
           estado = YENDO_ABAJO;
       } break;
       case YENDO_ARRIBA:{
         piso_actual = comprobacion_piso();
         if (piso_nuevo == piso_actual)
           estado = DETENIDO;        
       } break;
       case YENDO_ABAJO:{
         piso_actual = comprobacion_piso();
         if (piso_nuevo == piso_actual)
           estado = DETENIDO;    
       } break;
     }
   }
}

Como se ve arriba, la MEF se codifica generalmente en un bloque "switch - case". Todos los estados del sistema están definidos en una enumeración "enum { ... }" y la variable "estado" almacena el estado actual del sistema.

Cada opción "case" representa un estado particular de la MEF:

case DETENIDO:{ ... }
case YENDO_ARRIBA:{ ... }
case YENDO_ABAJO:{ ... }

Las transiciones en la MEF se codifican mediante una reasignación de un nuevo estado a la variable de estado:

estado = YENDO_ARRIBA;
estado = DETENIDO;

Las condiciones de transición se codifican mediante sentencias condicionales "if - else" asociadas a una determinada transición:

if (piso_nuevo > piso_actual) ... else ...
if (piso_nuevo < piso_actual) ... else ...

En una MEF se asocian acciones o respuestas del sistema (salidas) ya sea con los mismos estados o con las transiciones, por ejemplo, al pasar del estado DETENIDO al estado YENDO_ARRIBA, se activa el motor correspondiente que mueve el ascensor hacia arriba. Al llegar al nuevo piso (cambio de estado de YENDO_ARRIBA a DETENIDO) el motor se desactiva; por supuesto estos detalles han sido omitidos en el ejemplo por conveniencia para no complicar la descripción del mismo.

Las Máquinas de Estado Finito no son Diagramas de Flujo

Las MEF no son diagramas de flujo y no deben confundirse con los mismos. En una MEF las acciones se asocian con las flechas (transiciones), mientras que un Diagrama de Flujo las acciones se asocian a los vértices de la flecha o a los bloques de proceso. Cuando una MEF se encuentra en uno de sus estados, básicamente se encuentra "en reposo" esperando a que suceda un evento, mientras que en un Diagrama de Flujo el sistema se encuentra activo realizando una tarea.

Comparación Máquina de Estado Finito y Diagrama de Flujo

Tipos de Máquinas de Estado Finito

Existen principalmente dos tipos de Máquinas de Estado Finito: Las Reconocedoras o Detectoras y las Transductoras.

Reconocedoras o Detectoras: Llamadas también Detectoras de Secuencia, realizan básicamente la detección de patrones o secuencias determinadas en respuesta a las entradas recibidas. Por su definición teórica este tipo de sistema no proveen señales de salida (acciones), simplemente transicionan desde un estado inicial a un estado final de "Exito", en cuyo caso se entiende que un patrón o secuencia ha sido reconocida exitosamente. Las MEF Detectoras de Secuencia son útiles en aplicaciones en las que se necesita verificar contraseñas, códigos o la validación de paquetes de datos en transmisión digital, este último un ejemplo muy típico de su uso. A continuación se muestra el ejemplo de una verificación de un código / contraseña con una MEF Detectora de Secuencia:

Máquina de Estado Finito Detectora

En este ejemplo el único patrón que la MEF aceptará y reconocerá es: 57936. (En realidad cualquier patrón más largo que contenga la secuencia anterior, como: 1257936 o 5793688 será también reconocido por la MEF, sin embargo la verificación de estos casos se ha omitido en el ejemplo por simplicidad).

El estado inicial de la MEF es el denominado "Ninguno". Cualquier evento (número) diferente a 5 causará una transición al mismo estado y sólo la recepción de un "5" causará la transición al estado "1 Bueno". La recepción de un "7" en el estado "1 Bueno" causará una transición al estado "2 Buenos", cualquier otro valor diferente causará una transición a "Ninguno", lo cual obliga a reiniciar todo el proceso; y así sucesivamente hasta llegar al estado "4 Buenos".

En el estado "4 Buenos", un "6" causará una transición a "Abierto". A dicha transición está asociada una acción (salida) del sistema, la cual consiste en "desasegurar" (por ejemplo: abrir una cerradura). Cualquier otro valor diferente de "6" obliga a reiniciar el proceso desde "Ninguno".

En el estado "Abierto", un evento "cerrar" (por ejemplo, cerrar la puerta asociada a la cerradura) causará que el sistema transicione a "Ninguno" y a dicha transición viene también asociada una acción o salida del sistema que consiste en "asegurar" el sistema (cerrojo).

Transductoras: Las MEFs transductoras se caracterizan por generar acciones o salidas dependiendo de las entradas y/o estados; se implementan en sistemas embebidos típicamente para aplicaciones de control. Un ejemplo de este tipo de sistema es el ejemplo del ascensor ya analizado en la primera parte de este artículo.

Ventajas de las Máquinas de Estado Finito

Son intuitivas y fáciles de entender.
Abstraen convenientemente detalles secundarios que no son necesarios para el análisis del sistema a un alto nivel y se centran en aspectos claves del mismo.
Aportan un componente visual que facilita el análisis y diseño del sistema.
Son universalmente aplicables.
Su uso es común un sistemas de transmisión de datos y el uso de protocolos de comunicación.
En programación minimiza grandemente la tendencia a escribir "código espagueti" y puede ayudar a reducir la cantidad de variable globales necesarias, aumentando al mismo tiempo la confiabilidad del sistema.

Desventajas de las Máquinas de Estado Finito

No son aplicables a todos los problemas de diseño.
Funcionan bien en sistemas pequeños con una cantidad de estados en el orden de las decenas.
No funcionan bien en sistemas con una cantidad de estados en el orden de las centenas o miles de estados, aunque en estos casos es posible la estructuración mediante una combinación de MEFs más pequeñas.
La adición de funcionalidad es un poco inflexible.
Son "planas" por naturaleza, no poseen estructura definida y no permiten una jerarquización de los componentes que minimize la repetición innecesaria de ciertos estados. Una mejor alternativa en este caso es el uso de las Cartillas de Estado (Statecharts) y el uso de UML (Unified Modelling Language).
Es fácil caer en el error de definir demasiados estados para el sistema, lo cual minimiza la eficiencia, o de definir menos estados de lo que es necesario, lo cual contradice al propósito de las MEFs de reducir la cantidad de código convolucionado (demasiadas sentencias condicionales del tipo "if - then - else").

Finalmente

Casi todos los que trabajamos, estudiamos o experimentamos con sistemas embebidos hemos dado nuestros primeros pasos en la programación de sistemas embebidos escribiendo el llamado "código espagueti". Algunos hemos llegado a usar con relativa seguridad el patrón de programación conocido como "Plano Principal / Plano Secundario" (Backgroud / Foreground) el cual implica el uso de interrupciones; aunque la realidad prueba que muchos estudiantes universitarios o egresados de electrónica o otras carreras afines que tienen que ver con diseño embebido no han llegado a dominar adecuadamente el uso de interrupciones (hago énfasis en la palabra "adecuadamente").

Cuánto menos conocido y entendido es el uso del patrón de programación con Máquinas de Estado Finito, las cuales, no es de sorprenderse, son una herramienta cuyo uso está ampliamente extendido en el ámbito del desarrollo de sistemas embebidos de primer nivel. Muchos desarrolladores profesionales han recomendado en repetidas ocasiones que, cualquier sistema reactivo que se preste al diseño con Máquinas de Estado Finito (pues, obviamente, no todos se prestan, pero sí una mayoría), debería hacer uso de este patrón de programación, debido a que éste provee un abstracción del sistema que resulta natural, segura, fácil de entender y que puede ser muy eficiente.

Si aún no lo has hecho, es hora de darle a las Máquinas de Estado Finito un uso más frecuente. Con toda seguridad encontrarás que tus proyectos se simplifican en gran manera, aunque por supuesto, dominar el uso de las Máquinas de Estado Finito requiere que uno pase un buen tiempo estudiándolas y usándolas.

Raúl Alvarez Torrico
www.TecBolivia.com