Máquina de Estados

MAQUINA DE ESTADOS FINITOS

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.

En pocas palabras una máquina de estados es una conceptualización de un circuito secuencial particular la cual representa un sistema como un conjunto de estados, de transiciones entre ellos junto con las entradas y salidas asociadas

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.

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:

*Selección_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.

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:

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 observado anteriormente.

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").

MÁQUINA DE MOORE

Las salidas dependen sólo del estado presente

Las entradas intervienen en la decisión del próximo estado

Z = f(y)

Diagramas de estado de máquinas de Moore

Las salidas de las máquinas de Moore se muestran dentro del círculo del estado

La salida está asociada al estado y sólo cambia cuando cambia el estado

MÁQUINA DE MEALY

Las salidas dependen del estado presente y del valor de las entradas

Z = f(y,X)

Diagramas de estado de máquinas de Mealy

Las máquinas de Mealy generan sus salidas en base a:

• El estado presente

• Los valores de las entradas

Es capaz de generar salidas diferentes en un mismo estado

Los valores de las salidas se muestran en las transiciones, porque se calculan de la misma forma que los próximos estados

REFERENCIAS

R. Alvares (2021, noviembre 10)  "Introducción a las Máquinas de Estado Finito" [Online]. Available on: http://tecbolivia.com/index.php/articulos-y-tutoriales-microcontroladores/13-introduccion-a-las-maquinas-de-estado-finito

DTe (s.f) "Tema 2: Análisis y diseño de circuitos digitales" [Online]. Available on: https://www.dte.us.es/docencia/eps/giei/ed/teoria/tema2ppt

Openlibra (s.f) "Máquinas de Estados Finitos" [Online]. Available on: https://openlibra.com/es/book/maquinas-de-estados-finitos

E. Vílchez (s.f) "Máquinas de estado finito y autómatas" [Online]. Available on: https://www.escinf.una.ac.cr/discretas/Archivos/Presentaciones/Capitulo_7.pdf

"