Maquinas de Estado Finito




MÁQUINAS DE ESTADO FINITO

DESCRIPCIÓN FORMAL DE LA MÁQUINA DE ESTADO FINITO

Es un Modelo abstracto de una máquina con memoria interna primitiva. Se puede considerar a un computador como una máquina de este tipo. Una Máquina de Estado Finito M consiste en:
a) Un conjunto finito I de símbolos de entrada.
b) Un conjunto finito O de símbolos de salida.
c) Un conjunto finito Sde estados.
d) Una función estado siguiente f de S X I en S .
e) Una función salida g de S X I en O .
f ) Un estado inicial o , incluido en S.

Se expresa con una descripción formal como M = ( I , O , S , f, g, 0 ).

En este caso, los símbolos de entrada y salida no deben ser necesariamente diferentes, sino más bien, según sea requerido en la especificación del diseño.Nótese que se trata de símbolos, como los que se emplearon en los módulos anteriores.


DESCRIPCIÓN NO FORMAL DE LA MÁQUINA DE EDO. FINITO

Se trata de un modelo matemático, representado con recursos formales (que se especificarán posteriormente), y que puede emplearse para representar o simular el funcionamiento de un sistema real, que puede ser electrónico o computacional o de otro tipo. Ésto esmuy útil, ya que posteriormente al diseño formal, se puede implementar en forma sencilla por medio de un programa escrito en cualquier lenguaje de programación.

Los sistemas que se pueden representar por medio de este modelo matemático contienen una única entrada y una sola salida, y son todos aquellos en los que no basta con conocer el valor de la entrada para conocer la salida. En estecaso, existe un parámetro muy importante, llamado estado actual del sistema, y que en combinación con la entrada, ambos sí determinan una salida bien definida.

En una Máquina de Estado Finito, ocurre lo que se conoce como una Transición, una acción que consta de tres partes. Consiste en que al llegar un símbolo de entrada, el modelo responda primero con la producción de un símbolo en la salida yposteriormente (pero de manera inmediata) exista un cambio a un nuevo estado. Dicha transición es la unidad de operación en una Máquina de Estado Finito.

Es muy importante que primero se produzca la salida, antes del cambio de estado.

En este modelo se presentan dos funciones, de las mismas dos variables:

Símbolo de salida = f (estado actual, símbolo de entrada) = g. // Función g.Estado siguiente = f (estado actual, símbolo de entrada) = f. // Función f.

Veamos un ejemplo, como si la Máquina fuera una "caja negra":


En la Máquina de la figura anterior supondremos, para ejemplificar, que si la entrada es una a, y el estado actual fuese B, la salida sería un 0. Sin embargo, si el estado actual fuese D, por ejemplo, la salida podría ser 1, aún con la mismaentrada a.

Se recalca que se emplea este modelo para SIMULAR todos aquellos sistemas en los que la salida no es función exclusiva de la entrada, sino también de un estado o situación actual implícita en el mismo.


EJEMPLOS SENCILLOS DE APLICACIONES DE MÁQUINAS DE ESTADO FINITO:

1 Máquina para venta de refrescos.
Ya que el estado actual (cantidad de dinero que se ha depositado en ella)junto con la entrada actual (la moneda que se está depositando en cada momento) determinan la salida que el aparato entrega (nada, cambio, refresco, refresco y cambio). La misma moneda produce diferentes salidas.

2 Cajero automático.
Ya que la entrada (tarjeta, NIP, botón) debe combinarse con una correcta serie de transiciones por los estados (espera usuario, espera NIP, espera requisición deservicio, etc.) para que se pueda obtener la salida deseada (billetes, impresiones de estado de cuenta, etc.). La entrada "solicito $100" en el estado "espera NIP" no produce el efectivo requerido.

3 Circuitos secuenciales digitales.
Ya que en los circuitos de este tipo, es necesario conocer el potencial o voltaje que guardan ciertos puntos dentro de los mismos (es decir, los estados) para...