martes, 3 de julio de 2012

Maquina de estado finito.

Maquina de Estado Finito.



   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.


    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; ejemplos 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:


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

2 comentarios:

  1. 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

    ResponderEliminar
  2. Este comentario ha sido eliminado por el autor.

    ResponderEliminar