Máquinas de Mealy y Moore en TOC

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.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *