Maquinas Secuenciales

Las máquinas de estados finitos suelen denominarse máquinas secuenciales ya que a partir de un estado inicial y de una secuencia ordenada de eventos de entrada, generan una secuencia de estados por los que pasa la máquina, y a su vez una secuencia de acciones de salida. Una máquina secuencial es aquella que su salida depende, además de sus entradas, de los estados anteriores del sistema (el sistema tiene memoria)

Las máquinas secuenciales son un poderoso modelo para implementar esquemas de control secuencial (dependientes de la historia pasada), tanto en hardware como en software. El modelo de máquina secuencial también facilita el diseño de la programación de sistemas multitareas, en tiempo real, utilizando microcontroladores.

El modelo de máquina secuencial se emplea en Teoría de lenguajes formales y tiene importantes aplicaciones en reconocimiento de patrones y analizadores léxicos y sintácticos, por mencionar algunas.

Historia

Una de las primeras máquinas secuenciales fue el telar de Jacquard, que en 1804, hacía diseños de telas programados en tarjetas perforadas. Hacia 1822, el inglés Charles Babbage, combina las tarjetas perforadas del telar de Jacquard con una calculadora mecánica, para iniciar la construcción de la “Máquina diferencial” para hacer cálculos astronómicos y científicos repetitivos.

Las primeras computadoras eran básicamente una calculadora con dos memorias, una para almacenar el programa que activa las funciones aritméticas y lógicas y otra memoria para almacenar resultados numéricos temporales. A esta arquitectura, se le llama arquitectura Harvard.

John Von Newman, de la Universidad de Princeton, propuso usar una sola memoria tanto para datos como para programa. Con ello se optimiza el uso de la memoria. En la actualidad, prácticamente todas las computadoras son del tipo Von Newman. Se dice que esta arquitectura sufre del “Cuello de botella de Von Newman”. Ya que sólo puede direccionar un dato a la vez.

Máquina de Mealy

Una máquina de Mealy es un tipo de máquina de estados finitos que genera una salida basándose en su estado actual y una entrada. Esto significa que el Diagrama de estados incluirá ambas señales de entrada y salida para cada línea de transición. En contraste, la salida de una máquina de Moore de estados finitos (el otro tipo) depende solo del estado actual de la máquina, dado que las transiciones no tienen entrada asociada. Sin embargo, para cada Máquina de Mealy hay una máquina de Moore equivalente cuyos estados son la unión de los estados de la máquina de Mealy y el Producto cartesiano de los estados de la máquina de Mealy y el alfabeto de entrada.

Su nombre viene dado por George H. Mealy, un pionero de las máquinas de estados, quien escribió Un Método para sintetizar Circuitos Secuenciales en Septiembre de 1955.

Las máquinas de Mealy suministran un modelo matemático rudimentario y eficiente para las máquinas de cifrado. Considerando el alfabeto de entrada y salida del alfabeto Latino, por ejemplo, entonces una máquina de Mealy puede ser diseñada para darle una cadena de letras (una secuencia de entradas), esto puede procesarlo en un string cifrado (una secuencia de salidas). Sin embargo, aunque se podría probablemente usar un modelo de Mealy para describir una Máquina Enigma, el diagrama de estados sería demasiado complejo para suministrar medios factibles de diseñar máquinas de cifrado complejas.

Máquina de Moore

Una máquina de Moore es un autómata de estados finitos para el cual la salida en un momento dado sólo depende de su estado en ese momento, mientras la transición al siguiente estado depende del estado en que se encuentre y de la entrada introducida. El diagrama de estados para una máquina Moore incluirá una señal de salida para cada estado. Comparada con la Máquina de Mealy, la cual mapea transiciones en la máquina a salidas.

El nombre Maquina de Moore viene dado por Edward F. Moore, un pionero de las máquinas de estados, quien escribió Gedanken-experiments on Sequential Machines en 1956.

La mayoría de las máquinas electrónicas están diseñadas como sistemas secuenciales síncronos. Los sistemas secuenciales síncronos son una forma restringida de máquinas de Moore donde el estado cambia solo cuando la señal de reloj global cambia. Normalmente el estado actual se almacena en Flip-flops, y la señal de reloj global está conectada a la entrada "clock" de los flip-flops. Los sistemas secuenciales síncronos son una manera de resolver problemas de Metaestabilidad.