Máquina harinosa

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 sus 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, es posible como máximo una transición.

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

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

• un conjunto finito de estados${\displaystyle S}$
• un estado inicial (también llamado estado de partida)${\displaystyle S_{0}}$que es un elemento de${\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${\displaystyle T:S\times \Sigma \rightarrow S}$mapeo de pares de un estado y un símbolo de entrada al siguiente estado correspondiente.
• una función de salida${\displaystyle G:S\times \Sigma \rightarrow \Lambda }$mapeo de pares de un estado y un símbolo de entrada al símbolo de salida correspondiente.

En algunas formulaciones, las funciones de transición y de 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 con el tiempo en "pulsos de temporizador" discretos.${\displaystyle t_{0},t_{1},t_{2},...}$y reaccionar de acuerdo con su configuración interna en esos instantes idealizados, o bien hacer que la máquina de estados espere un siguiente símbolo de entrada (como en una FIFO) y reaccione cuando llegue.

1. Las máquinas harinosas tienden a tener menos estados:
   • Diferentes resultados en arcos ( n2 ⁾ en lugar de estados ( n ).
2. Cuando se implementan como circuitos electrónicos (en lugar de como abstracciones matemáticas o código):
   • Las máquinas Moore son más seguras de usar que las máquinas Mealy:
     • Las salidas cambian en el flanco del reloj (siempre un ciclo después).
     • En las máquinas de Mealy, un cambio en la entrada puede provocar un cambio en la salida tan pronto como se realiza la lógica, lo cual es un gran problema cuando dos máquinas están interconectadas; puede producirse una retroalimentación asíncrona si no se tiene cuidado.
   • Las máquinas harinosas reaccionan más rápido a las entradas:
     • Reaccionan en el mismo ciclo; no necesitan esperar a que el reloj avance.
     • En las máquinas de Moore, puede ser necesaria más lógica para decodificar el estado en salidas, lo que implica mayores retardos de puerta tras el flanco del reloj.

El diagrama de estados de una máquina de Mealy asocia un valor de salida con cada arista de transición, a diferencia del diagrama de estados de una máquina de 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 de hélice ( S × Σ, ( x , i ) → ( T ( x , i ), G ( x , i ))) . ^{[ 2 ]} Este grafo tiene como vértices los pares de estado y letras, cada nodo tiene grado de salida uno, y el sucesor de ( x , i ) es el siguiente estado del autómata y la letra que el autómata produce 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 birreversible .

Las máquinas de Mealy proporcionan un modelo matemático rudimentario para las máquinas de cifrado. Si consideramos el alfabeto latino como alfabeto de entrada y salida , por ejemplo, se puede diseñar una máquina de Mealy que, dada una cadena de letras (una secuencia de entradas), la procese para obtener una cadena cifrada (una secuencia de salidas). Sin embargo, aunque un modelo de Mealy podría usarse para describir la máquina Enigma , el diagrama de estados sería demasiado complejo para proporcionar un método viable para diseñar máquinas de cifrado complejas.

Las máquinas de Moore/Mealy son autómatas finitos deterministas ( AFD) que generan una salida en cada ciclo de reloj. Las CPU modernas, las computadoras, los teléfonos celulares, los relojes digitales y los dispositivos/máquinas electrónicas básicas cuentan con algún tipo de máquina de estados finitos para su control.

Los sistemas de software sencillos, en particular aquellos que pueden representarse mediante expresiones regulares , pueden modelarse como máquinas de estados finitos. Existen muchos sistemas sencillos de este tipo, como las máquinas expendedoras o los dispositivos electrónicos básicos.

Al encontrar la intersección de dos máquinas de estados finitos, se pueden diseñar de forma muy sencilla sistemas concurrentes que intercambien mensajes, por ejemplo. Un semáforo, por ejemplo, es un sistema compuesto por múltiples subsistemas, como los distintos semáforos, que funcionan simultáneamente.

• Circuito síncrono
• Máquina de Moore
• Máquina de estados algorítmica
• Controlador Richards

• 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 . Estudios de Cambridge en Matemáticas Avanzadas. 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 la finitud para (semi)grupos de autómatas". International Journal of Algebra and Computation . 22 (6). arXiv : 1105.4725 . Bibcode : 2011arXiv1105.4725A . doi : 10.1142/S021819671250052X . S2CID 47518684 . Zbl 1280.20038 .  

• Contenido multimedia relacionado con la máquina de Mealy en Wikimedia Commons.