Máquina de Mealy

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar al autor principal del artículo en su página de discusión pegando: {{subst:Aviso referencias|Máquina de Mealy}} ~~~~

Este artículo o sección necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 4 de junio de 2011. También puedes ayudar wikificando otros artículos o cambiando este cartel por uno más específico.

El diagrama de estados de una máquina de Mealy simple

En la teoría de la computación, 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.

Origen del nombre

El nombre "Máquina de Mealy" viene del promotor del concepto: G. H. Mealy, un pionero de las máquinas de estados, quien escribió Un Método para sintetizar Circuitos Secuenciales, Bell System Tech. J. vol 34, pp. 1045–1079, September 1955.

Diseño

Las máquinas de Mealy suministran un modelo matemático rudimentario 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.

Definición formal

Una máquina de Mealy es una 6-tupla, (S, S0, Σ, Λ, T, G), consistiendo en un conjunto finito de estados (S) un estado inicial S0 el cual es un elemento de (S) un conjunto finito llamado el alfabeto entrada (Σ) un conjunto finito llamado el alfabeto salida (Λ) una función de transiciones (T : S × Σ → S) una función de salida (G : S × Σ → Λ)

Véase también

• Máquina de Moore