Moore y Mealy Machines

Los autómatas finitos pueden tener salidas correspondientes a cada transición. Hay dos tipos de máquinas de estados finitos que generan resultados:

  • Máquina harinosa
  • Máquina de moore

Máquina harinosa

Una Mealy Machine es un FSM cuya salida depende tanto del estado actual como de la entrada actual.

Se puede describir mediante una tupla de 6 (Q, ∑, O, δ, X, q 0 ) donde -

  • Q es un conjunto finito de estados.

  • es un conjunto finito de símbolos llamado alfabeto de entrada.

  • O es un conjunto finito de símbolos llamado alfabeto de salida.

  • δ es la función de transición de entrada donde δ: Q × ∑ → Q

  • X es la función de transición de salida donde X: Q × ∑ → O

  • q0es el estado inicial desde donde se procesa cualquier entrada (q 0 ∈ Q).

La tabla de estado de una máquina de harina se muestra a continuación:

Estado actual Siguiente estado
entrada = 0 entrada = 1
Estado Salida Estado Salida
→ un segundo x 1 C x 1
segundo segundo x 2 re x 3
C re x 3 C x 1
re re x 3 re x 2

El diagrama de estado de la Mealy Machine anterior es:

Máquina de Moore

La máquina de Moore es una FSM cuyas salidas dependen únicamente del estado actual.

Una máquina de Moore se puede describir mediante una tupla de 6 (Q, ∑, O, δ, X, q 0 ) donde -

  • Q es un conjunto finito de estados.

  • es un conjunto finito de símbolos llamado alfabeto de entrada.

  • O es un conjunto finito de símbolos llamado alfabeto de salida.

  • δ es la función de transición de entrada donde δ: Q × ∑ → Q

  • X es la función de transición de salida donde X: Q → O

  • q0es el estado inicial desde donde se procesa cualquier entrada (q 0 ∈ Q).

La tabla de estado de una máquina Moore se muestra a continuación:

Estado actual Estado siguiente Salida
Entrada = 0 Entrada = 1
→ un segundo C x 2
segundo segundo re x 1
C C re x 2
re re re x 3

El diagrama de estado de la máquina de Moore anterior es:

Mealy Machine vs.Moore Machine

La siguiente tabla destaca los puntos que diferencian una máquina harinosa de una máquina Moore.

Máquina harinosa Máquina de Moore
La salida depende tanto del estado actual como de la entrada actual La salida depende solo del estado actual.
Generalmente, tiene menos estados que Moore Machine. Generalmente, tiene más estados que Mealy Machine.
El valor de la función de salida es una función de las transiciones y los cambios, cuando se realiza la lógica de entrada en el estado actual. El valor de la función de salida es una función del estado actual y los cambios en los bordes del reloj, siempre que se produzcan cambios de estado.
Las máquinas harinosas reaccionan más rápido a las entradas. Generalmente reaccionan en el mismo ciclo de reloj. En las máquinas Moore, se requiere más lógica para decodificar las salidas, lo que genera más retrasos en el circuito. Generalmente reaccionan un ciclo de reloj más tarde.

Máquina de Moore a máquina harinosa

Algoritmo 4

Input - Máquina de Moore

Output - Máquina harinosa

Step 1 - Tome un formato de tabla de transición de Mealy Machine en blanco.

Step 2 - Copie todos los estados de transición de Moore Machine en este formato de tabla.

Step 3- Verificar los estados actuales y sus correspondientes salidas en la tabla de estados de Moore Machine; si para un estado Q i la salida es m, cópiela en las columnas de salida de la tabla de estado de Mealy Machine dondequiera que Q i aparezca en el siguiente estado.

Ejemplo

Consideremos la siguiente máquina de Moore:

Estado actual Estado siguiente Salida
a = 0 a = 1
→ un re segundo 1
segundo una re 0
C C C 0
re segundo una 1

Ahora aplicamos el algoritmo 4 para convertirlo en Mealy Machine.

Step 1 & 2 -

Estado actual Estado siguiente
a = 0 a = 1
Estado Salida Estado Salida
→ un re segundo
segundo una re
C C C
re segundo una

Step 3 -

Estado actual Estado siguiente
a = 0 a = 1
Estado Salida Estado Salida
=> a re 1 segundo 0
segundo una 1 re 1
C C 0 C 0
re segundo 0 una 1

Mealy Machine a Moore Machine

Algoritmo 5

Input - Máquina harinosa

Output - Máquina de Moore

Step 1- Calcule el número de salidas diferentes para cada estado (Q i ) que están disponibles en la tabla de estados de la máquina Mealy.

Step 2- Si todas las salidas de Qi son iguales, copie el estado Q i . Si tiene n salidas distintas, divida Q i en n estados como Q en donden = 0, 1, 2 .......

Step 3 - Si la salida del estado inicial es 1, inserte un nuevo estado inicial al principio que da una salida 0.

Ejemplo

Consideremos la siguiente máquina harinosa:

Estado actual Estado siguiente
a = 0 a = 1
Estado siguiente Salida Estado siguiente Salida
→ un re 0 segundo 1
segundo una 1 re 0
C C 1 C 0
re segundo 0 una 1

Aquí, los estados 'a' y 'd' dan solo salidas 1 y 0 respectivamente, por lo que retenemos los estados 'a' y 'd'. Pero los estados 'b' y 'c' producen salidas diferentes (1 y 0). Entonces, dividimosb dentro b0, b1 y c dentro c0, c1.

Estado actual Estado siguiente Salida
a = 0 a = 1
→ un re b 1 1
b 0 una re 0
b 1 una re 1
c 0 c 1 C 0 0
c 1 c 1 C 0 1
re b 0 una 0