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.
0 comentarios:
Publicar un comentario