Una
Máquina de Estado Finito, 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,
cual es el caso de la mayoría de los sistemas embebidos basados en micro
controladores o microprocesadores.
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 micro controladores 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.
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:
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.
Codificación en Lenguaje C.
El sistema de control del ascensor se puede codificar en
Lenguaje C de la siguiente manera:
01./* Ejemplo de Máquina de Estado Finito
para un ascensor simplificado */
02.enum
eEstados { // Los estados
se la MEF se definen en una enumaración
03.DETENIDO,
04.YENDO_ARRIBA,
05.YENDO_ABAJO
06.} estado;
07.
08.int
piso_nuevo, piso_actual;
09.main() {
10.estado = DETENIDO; //
La MEF se inicializa en estado DETENIDO
11.while
(TRUE) {
12.switch
(estado) {
13.case
DETENIDO:{ //
14.// Verificar si se ha seleccionado un
nuevo piso:
15.piso_nuevo =
seleccion_piso();
16.if
(piso_nuevo > piso_actual)
17.estado = YENDO_ARRIBA;
18.else
if
(piso_nuevo < piso_actual)
19.estado = YENDO_ARRIBA;
20.} break;
21.case
YENDO_ARRIBA:{
22.piso_actual = comprobacion_piso();
23.if
(piso_nuevo == piso_actual)
24.estado =
DETENIDO;
25.} break;
26.case
YENDO_ABAJO:{
27.piso_actual = comprobacion_piso();
28.if
(piso_nuevo == piso_actual)
29.estado = DETENIDO;
30.} break;
31.}
32.}
33.}
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:{ ... }
estado = YENDO_ARRIBA;
estado = DETENIDO;
if (piso_nuevo > piso_actual) ... else ...
if (piso_nuevo < piso_actual) ... else ...
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
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:
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 asi 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 variables 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 órden de las
decenas.
- No
funcionan bien en sistemas con una cantidad de estados en el órden 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").
Borrero Daniel
Luimar Abreu
Cardenas Zoraida
Sosa Dubal
Esta información es plagio de la página original, te recomiendo que des crédito a la página original que hizo esta información
ResponderEliminarEste comentario ha sido eliminado por el autor.
ResponderEliminar