Máquinas de Mealy y Moore en TOC – Part 1

Máquinas de Moore:  Las máquinas de Moore son máquinas de estado finito con valor de salida y su salida depende solo del estado actual. Se puede definir como (Q, q0,  ∑,  O, δ, λ) donde:

• Q es un conjunto finito de estados.
• q0 es el estado inicial.
• ∑  es el alfabeto de entrada.
• O es el alfabeto de salida.
• δ es la función de transición que mapea Q× ∑  → Q.
• λ es la función de salida que mapea Q → O.

Figure 1

En la máquina de Moore que se muestra en la Figura 1, la salida se representa con cada estado de entrada separado por /. La longitud de la salida de una máquina Moore es mayor que la entrada en 1.

• Entrada:  11
• Transición:  δ (q0,11)=> δ(q2,1)=>q2
• Salida:  000 (0 para q0, 0 para q2 y nuevamente 0 para q2)

 Máquinas harinosas:  las máquinas harinosas también son máquinas de estado finito con valor de salida y su salida depende del estado actual y el símbolo de entrada actual. Se puede definir como (Q, q0,  ∑,  O, δ, λ’) donde:

• Q es un conjunto finito de estados.
• q0 es el estado inicial.
• ∑  es el alfabeto de entrada.
• O es el alfabeto de salida.
• δ es la función de transición que mapea Q× ∑  → Q.
• ‘λ’ es la función de salida que mapea Q× ∑ → O.

Figure 2

En la máquina harinosa que se muestra en la Figura 1, la salida se representa con cada símbolo de entrada para cada estado separado por /. La duración de la salida de una máquina harinosa es igual a la duración de la entrada.

• Entrada: 11
• Transición:  δ (q0,11)=> δ(q2,1)=>q2
• Salida:  00 (la transición de q0 a q2 tiene Salida 0 y la transición de q2 a q2 también tiene Salida 0)

NOTA :

Si hay n entradas en la máquina Mealy, genera n salidas, mientras que si hay n entradas en la máquina Moore, genera n + 1 salidas. 

Conversión de Mealy a Moore Machine

Tomemos la tabla de transición de la máquina harinosa que se muestra en la Figura 2.

	Entrada=0		Entrada=1
Estado actual	Estado siguiente	Producción	Estado siguiente	Producción
q0	q1	0	q2	0
q1	q1	0	q2	1
q2	q1	1	q2	0

tabla 1

Paso 1.  Primero averigüe aquellos estados que tienen más de 1 salida asociada con ellos. q1 y q2 son los estados que tienen asociada la salida 0 y 1.

Paso 2.  Crea dos estados para estos estados. Para q1, dos estados serán q10 (estado con salida 0) y q11 (estado con salida 1). De manera similar para q2, dos estados serán q20 y q21.

Paso 3.  Cree una máquina moore vacía con un nuevo estado generado. Para la máquina Moore, la salida se asociará a cada estado independientemente de las entradas.

	Entrada=0	Entrada=1
Estado actual	Estado siguiente	Estado siguiente	Producción
q0
q10
q11
q20
q21

Tabla 2

Paso 4.  Llene las entradas del siguiente estado utilizando la tabla de transición de la máquina harinosa que se muestra en la Tabla 1. Para q0 en la entrada 0, el siguiente estado es q10 (q1 con salida 0). De manera similar, para q0 en la entrada 1, el siguiente estado es q20 (q2 con salida 0). Para q1 (tanto q10 como q11) en la entrada 0, el siguiente estado es q10. De manera similar, para q1 (tanto q10 como q11), el siguiente estado es q21. Para q10, la salida será 0 y para q11, la salida será 1. De manera similar, se pueden completar otras entradas.

	Entrada=0	Entrada=1
Estado actual	Estado siguiente	Estado siguiente	Producción
q0	q10	q20	0
q10	q10	q21	0
q11	q10	q21	1
q20	q11	q20	0
q21	q11	q20	1

Tabla 3

Esta es la tabla de transición de la máquina Moore que se muestra en la Figura 1.

Conversión de máquina moore a máquina harinosa

Tomemos la máquina moore de la Figura 1 y su tabla de transición se muestra en la Tabla 3. Paso 1.  Construya una máquina harinosa vacía usando todos los estados de la máquina moore como se muestra en la Tabla 4.

	Entrada=0		Entrada=1
Estado actual	Estado siguiente	Producción	Estado siguiente	Producción
q0
q10
q11
q20
q21

Tabla 4

Paso 2:  el siguiente estado para cada estado también se puede encontrar directamente en la tabla de transición de la máquina Moore como:

	Entrada=0		Entrada=1
Estado actual	Estado siguiente	Producción	Estado siguiente	Producción
q0	q10		q20
q10	q10		q21
q11	q10		q21
q20	q11		q20
q21	q11		q20

Tabla 5

Paso 3:  Como podemos ver, la salida correspondiente a cada entrada en la tabla de transición de la máquina de Moore. Use esto para llenar las entradas de salida. p.ej; Las salidas correspondientes a q10, q11, q20 y q21 son 0, 1, 0 y 1 respectivamente.   

	Entrada=0		Entrada=1
Estado actual	Estado siguiente	Producción	Estado siguiente	Producción
q0	q10	0	q20	0
q10	q10	0	q21	1
q11	q10	0	q21	1
q20	q11	1	q20	0
q21	q11	1	q20	0

Tabla 6

 Paso 4:   Como podemos ver en la tabla 6, q10 y q11 son similares entre sí (mismo valor del siguiente estado y salida para entrada diferente). De manera similar, q20 y q21 también son similares. Entonces, q11 y q21 pueden eliminarse.

	Entrada=0		Entrada=1
Estado actual	Estado siguiente	Producción	Estado siguiente	Producción
q0	q10	0	q20	0
q10	q10	0	q21	1
q20	q11	1	q20	0

Tabla 7

Esta es la misma máquina harinosa que se muestra en la Tabla 1. Por lo tanto, hemos convertido la máquina harinosa en moore y hemos vuelto a convertir moore en harinosa.

Nota:  El número de estados en la máquina harinosa no puede ser mayor que el número de estados en la máquina moore.

Ejemplo:  ¿La máquina de estados finitos descrita por el siguiente diagrama de estados con A como estado inicial, donde una etiqueta de arco es x / y y x representa una entrada de 1 bit e y representa una salida de 2 bits? Emite la suma de los bits presentes y anteriores de la entrada. 

1. Da salida a 01 siempre que la secuencia de entrada contenga 11.
2. Da salida a 00 siempre que la secuencia de entrada contenga 10.
3. Ninguno de esos.

Solución:  Tomemos diferentes entradas y su salida y verifiquemos qué opción funciona:

Entrada:  01

Salida:  00 01 (Para 0, la salida es 00 y el estado es A. Luego, para 1, la salida es 01 y el estado será B)

Entrada:  11

Salida:  01 10 (Para 1, la Salida es 01 y el estado es B. Luego, para 1, la Salida es 10 y el estado es C)

Como podemos ver, está dando la suma binaria del bit actual y anterior. Para el primer bit, el bit anterior se toma como 0.

Este artículo es una contribución de Sonal Tuteja . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.