Maquina harinosa

Máquina cuya salida está determinada por su estado y entradas.

En la teoría de la computación , una máquina de Mealy es una máquina de estados finitos cuyos valores de salida están determinados tanto por su estado actual como por las entradas actuales. Esto contrasta con una máquina de Moore , cuyos valores de salida están determinados únicamente por su estado actual. Una máquina de Mealy es un transductor determinista de estados finitos : para cada estado y entrada, como máximo es posible una transición.

Historia

La máquina Mealy recibe su nombre de George H. Mealy , quien presentó el concepto en un artículo de 1955, "Un método para sintetizar circuitos secuenciales". ^[1]

Definición formal

Una máquina Mealy es una tupla de 6 que consta de lo siguiente: ${\displaystyle (S,S_{0},\Sigma ,\Lambda ,T,G)}$

• un conjunto finito de estados ${\displaystyle S}$
• un estado de inicio (también llamado estado inicial) que es un elemento de ${\displaystyle S_{0}}$ ${\displaystyle S}$
• un conjunto finito llamado alfabeto de entrada ${\displaystyle \Sigma }$
• un conjunto finito llamado alfabeto de salida ${\displaystyle \Lambda }$
• una función de transición que asigna pares de un estado y un símbolo de entrada al siguiente estado correspondiente. ${\displaystyle T:S\times \Sigma \rightarrow S}$
• una función de salida que asigna pares de un estado y un símbolo de entrada al símbolo de salida correspondiente. ${\displaystyle G:S\times \Sigma \rightarrow \Lambda }$

En algunas formulaciones, las funciones de transición y salida se fusionan en una sola función . ${\displaystyle T:S\times \Sigma \rightarrow S\times \Lambda }$

La "evolución a través del tiempo" se realiza en esta abstracción haciendo que la máquina de estados consulte el símbolo de entrada que cambia el tiempo en "tictacs del temporizador" discretos y reaccione de acuerdo con su configuración interna en esos instantes idealizados, o bien haciendo que la máquina de estados espere el siguiente símbolo de entrada (como en un FIFO) y reaccione cuando llega. ${\displaystyle t_{0},t_{1},t_{2},...}$

Comparación de las máquinas Mealy y las máquinas Moore

1. Las máquinas Mealy tienden a tener menos estados:
   • Diferentes salidas en arcos ( n ² ) en lugar de estados ( n ).
2. Cuando se implementan como circuitos electrónicos (en lugar de abstracciones matemáticas o códigos):
   • Las máquinas Moore son más seguras de utilizar que las máquinas Mealy:
     • Las salidas cambian en el borde del reloj (siempre un ciclo después).
     • En las máquinas Mealy, el cambio de entrada puede causar un cambio de salida tan pronto como se realiza la lógica, un gran problema cuando dos máquinas están interconectadas: puede ocurrir una retroalimentación asincrónica si uno no tiene cuidado.
   • Las máquinas Mealy reaccionan más rápido a las entradas:
     • Reaccionan en el mismo ciclo: no necesitan esperar el reloj.
     • En las máquinas de Moore, puede ser necesaria más lógica para decodificar el estado en salidas (más retrasos en las compuertas después del borde del reloj).

Diagrama

El diagrama de estados de una máquina Mealy asocia un valor de salida con cada borde de transición, en contraste con el diagrama de estados de una máquina Moore, que asocia un valor de salida con cada estado.

Cuando el alfabeto de entrada y salida son ambos Σ , también se puede asociar a un autómata de Mealy un grafo dirigido por hélice ^{[ aclaración necesaria ]} ( S × Σ, ( x , i ) → ( T ( x , i ), G ( x , i ))) . ^[2] Este grafo tiene como vértices las parejas de estado y letras, cada nodo es de grado de salida uno, y el sucesor de ( x , i ) es el siguiente estado del autómata y la letra que el autómata emite cuando está en el estado x y lee la letra i . Este grafo es una unión de ciclos disjuntos si el autómata es bireversible ^{[ definición necesaria ]} .

Ejemplos

Simple

Diagrama de estados de una máquina Mealy simple con una entrada y una salida. (Para cada valor de entrada, se obtiene 1 si el valor de entrada actual es diferente del anterior o 0 en caso contrario).

Una máquina Mealy simple tiene una entrada y una salida. Cada borde de transición está etiquetado con el valor de la entrada (mostrado en rojo) y el valor de la salida (mostrado en azul). La máquina comienza en el estado S _i . (En este ejemplo, la salida es la operación exclusiva-o de los dos valores de entrada más recientes; por lo tanto, la máquina implementa un detector de bordes, que emite un 1 cada vez que la entrada cambia y un 0 en caso contrario).

Complejo

Las máquinas Mealy más complejas pueden tener múltiples entradas y múltiples salidas. ^{[ cita requerida ]}

Aplicaciones

Las máquinas Mealy proporcionan un modelo matemático rudimentario para las máquinas de cifrado. Si se considera el alfabeto de entrada y salida (por ejemplo, el alfabeto latino ), se puede diseñar una máquina Mealy que, dada una cadena de letras (una secuencia de entradas), pueda procesarla y convertirla en una cadena cifrada (una secuencia de salidas). Sin embargo, aunque se podría utilizar un modelo Mealy para describir la Enigma , el diagrama de estados sería demasiado complejo para proporcionar medios viables de diseño de máquinas de cifrado complejas.

Las máquinas Moore/Mealy son DFA que también tienen salida en cualquier momento del reloj. Las CPU modernas, las computadoras, los teléfonos celulares, los relojes digitales y los dispositivos/máquinas electrónicos básicos tienen algún tipo de máquina de estados finitos para controlarlos.

Los sistemas de software simples, en particular los que se pueden representar mediante expresiones regulares , se pueden modelar como máquinas de estados finitos. Existen muchos sistemas simples de este tipo, como las máquinas expendedoras o la electrónica básica.

Al encontrar la intersección de dos máquinas de estados finitos, se pueden diseñar de manera muy sencilla sistemas concurrentes que intercambian mensajes, por ejemplo, un semáforo es un sistema que consta de múltiples subsistemas, como los diferentes semáforos, que funcionan de manera concurrente.

Algunos ejemplos de aplicaciones:

• clasificación de números
• reloj con temporizador
• máquina expendedora
• semáforo
• escáner de código de barras
• bombas de gasolina

Véase también

• Circuito sincrónico
• Máquina de Moore
• Máquina de estados algorítmica
• Controlador Richards

Notas al pie

1. Mealy, George H. (septiembre de 1955). "Un método para sintetizar circuitos secuenciales". Bell System Technical Journal . 34 (5): 1045–1079. doi :10.1002/j.1538-7305.1955.tb03788.x.
2. Akhavi y otros (2012)

Referencias

• Mealy, George H. (1955). Un método para sintetizar circuitos secuenciales . Bell System Technical Journal. págs. 1045–1079.
• Holcombe, WML (1982). Teoría de autómatas algebraicos . Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press . ISBN 0-521-60492-3.Zbl 0489.68046  .
• Roth, Charles H. Jr. (2004). Fundamentos del diseño lógico . Thomson-Engineering. pp. 364–367. ISBN 0-534-37804-8.
• Akhavi, Ali; Klimann, Ines; Lombardy, Sylvain; Mairesse, Jean; Picantin, Matthieu (2012). "Sobre el problema de finitud para (semi)grupos de autómatas". Revista Internacional de Álgebra y Computación . 22 (6). arXiv : 1105.4725 . Bibcode :2011arXiv1105.4725A. doi :10.1142/S021819671250052X. S2CID  47518684. Zbl  1280.20038.

Enlaces externos

• Medios relacionados con la máquina Mealy en Wikimedia Commons