Maquinas de estados

Maquinas de estados

Se denomina máquina de estados a un modelo de comportamiento de un sistema con entradas y salidas, en donde las salidas dependen no sólo de las señales de entradas actuales sino también de las anteriores. Las máquinas de estados se definen como un conjunto de estados que sirve de intermediario en esta relación de entradas y salidas, haciendo que el historial de señales deentrada determine, para cada instante, un estado para la máquina, de forma tal que la salida depende únicamente del estado y las entradas actuales.
Una máquina de estados se denomina máquina de estados finitos (FSM por finite state machine) si el conjunto de estados de la máquina es finito, este es el único tipo de máquinas de estados que podemos modelar en un computador en la actualidad; debido aesto se suelen utilizar los términos máquina de estados y máquina de estados finitos de forma intercambiable. Sin embargo un ejemplo de una máquina de estados infinitos sería un computador cuántico esto es debido a que los Qubit que utilizaría este tipo de computadores toma valores continuos, en contraposición los bits toman valores discretos (0 ó 1). Otro buen ejemplo de una máquina de estadosinfinitos es una Máquina universal de Turing la cual se puede definir teóricamente con una "cinta" o memoria infinita.
La representación de una máquina de estados se realiza mediante un Diagrama de estados, sin embargo también es posible utilizar un Diagrama de flujo.

Máquinas de Mealy y Moore
Las máquinas de Mealy y Moore son circuitos síncronos. Un circuito síncrono es un circuito digital enel cual sus partes están sincronizadas por una señal de reloj.
En un circuito síncrono ideal, cada cambio en los diferentes niveles lógicos es simultáneo. Estas transiciones se realizan después de un cambio de nivel de una señal llamada reloj. Idealmente la entrada a cada elemento de almacenamiento alcanza su valor final antes de que la siguiente señal de reloj ocurra, por lo tanto elcomportamiento de un circuito se puede predecir exactamente. Se requiere se cierto retardo para cada operación lógica, por lo que existe una máxima rapidez en el que cada sistema síncrono puede responder. El análisis de un diagrama de tiempos puede darnos esta rapidez.
Una máquina de Mealy es una máquina de estados finita, donde las salidas están determinadas por el estado actual y la entrada. Estosignifica que en el diagrama de estados se incluye una señal de salida para cada arista de transición. Por ejemplo, en la trayectoria de un estado 1 a un estado 2, si la entrada es cero la salida puede ser uno, y se debe poner sobre la arista la etiqueta “0/1”.
En contraste, la salida de una máquina de estado finito Moore (máquina de Moore), depende solo del estado actual y no depende de la entradaactual. Por lo tanto, los estados de una máquina de Moore son la unión de los estados de la máquina de Mealy y el producto cartesiano de estos estados y alfabeto de entrada (posibles entradas).

Diferencias

Maquina de Mealy | Maquina de Moore |
La salida depende del estado actual y de las entradas. | La salida depende sólo del estado actual. |
Por lo regular, tienen menos número de estados.| El número de estados es mayor o igual a la máquina de Mealy. |
Es menos estable. | Es más estable. |
Para probar un circuito, primero se hace el cambio en la entrada X y después se da el pulso de reloj. | Para probar un circuito, primero se da el pulso de reloj y después se hace el cambio en la entrada X. |
Las salidas se encuentran en la arista. | Las salidas se encuentran dentro delestado. |

Definición formal:
Una máquina de Moore se define como una tupla (secuencia finita) de 5{S, Σ, Λ, T, G} que consiste de:
• Un conjunto finito de estados (S)
• Un conjunto finito llamado alfabeto de entrada (Σ)
• Un conjunto finito llamado alfabeto de salida (Λ)
• Una función de transición (T: S × Σ → S) que dirige a cada estado y a una entrada al siguiente estado.
• Una función...