Máquina harinosa - Mealy machine

En la teoría de la computación , una máquina 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 (de Moore) están determinados únicamente por su estado actual. Una máquina Mealy es un transductor determinista de estado finito : para cada estado y entrada, como máximo es posible una transición.

Historia

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

Definicion formal

Una máquina Mealy es una tupla de 6 que consta de lo siguiente:

  • un conjunto finito de estados
  • un estado de inicio (también llamado estado inicial) que es un elemento de
  • un conjunto finito llamado alfabeto de entrada
  • un conjunto finito llamado alfabeto de salida
  • una función de transición que mapea pares de un estado y un símbolo de entrada al siguiente estado correspondiente.
  • una función de salida que mapea 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 salida se fusionan en una sola función .

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

  1. Las máquinas harinosas tienden a tener menos estados:
    • Diferentes salidas en arcos ( n 2 ) en lugar de estados ( n ).
  2. Las máquinas Moore son más seguras de usar:
    • Las salidas cambian en el borde del reloj (siempre un ciclo después).
    • En las máquinas de 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 retroalimentación asincrónica si uno no tiene cuidado.
  3. Las máquinas harinosas reaccionan más rápido a las entradas:
    • Reacciona en el mismo ciclo, no es necesario esperar al reloj.
    • En las máquinas de Moore, puede ser necesaria más lógica para decodificar el estado en las salidas: más retrasos de puerta después del borde del reloj.

Diagrama

El diagrama de estado de una máquina Mealy asocia un valor de salida con cada borde de transición, en contraste con el diagrama de estado 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 Mealy Automata un gráfico dirigido por Helix ( S × Σ, ( x , i ) → ( T ( x , i ), G ( x , i ))) . Esta gráfica tiene como vértices de las parejas de estado y de cartas, cada nodos son de uno a cabo grados, y el sucesor de ( x , i ) es el siguiente estado de los autómatas y la letra que la salida autómatas cuando es instaurar x y lee la letra i . Este gráfico es una unión de ciclos disjuntos si el autómata es bireversible.

Ejemplos de

Sencillo

Diagrama de estado de una máquina Mealy simple con una entrada y una salida.

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 arranca en el estado S i . (En este ejemplo, la salida es la exclusiva o de los dos valores de entrada más recientes; por lo tanto, la máquina implementa un detector de bordes, generando un uno cada vez que la entrada cambia y un cero en caso contrario).

Complejo

Las máquinas Mealy más complejas pueden tener múltiples entradas y múltiples salidas.

Aplicaciones

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

Las máquinas Moore / Mealy son DFA que también tienen salida en cualquier tic 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 estado finito 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 de estos sistemas simples, como máquinas expendedoras o electrónica básica.

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

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 gas

Ver también

Notas al pie

Referencias

enlaces externos