Autómatas finitos con salida (Conjunto 11)

Requisito previo: máquinas Mealy y Moore , diferencia entre la máquina Mealy y la máquina Moore 
En este artículo, veremos algunos diseños de autómatas finitos con salida, es decir, máquinas Moore y Mealy. 

Problema: Construcción de las máquinas que toman el número binario {0, 1} como entrada y producen el complemento a 1 de ese número como salida. 
Aquí se supone que la string de entrada se lee desde LSB (bit menos significativo) y se descarta el acarreo final. 
Aquí tenemos, 
Ε = {0, 1} y 
Δ = {0, 1} 
donde Ε y Δ son el alfabeto de entrada y salida respectivamente. 

La máquina de Moore requerida se construye a continuación: 
 

Explicación: 
en el diagrama anterior, el estado inicial ‘X’ al obtener ‘1’ como entrada, permanece en el estado de sí mismo e imprime ‘0’ como salida y al obtener ‘0’ como entrada transmite a un estado ‘Y’ e imprime ‘1’ como salida y así sucesivamente para los estados restantes. 

Por ejemplo, cuando la string de entrada es ‘101’, la máquina de Moore arriba produce una salida como ‘010’, que no es más que el complemento a 1 de la entrada dada, es decir, 1 se convierte en 0 y viceversa. 
Por lo tanto, finalmente, la máquina Moore anterior puede producir fácilmente el complemento a 1 de la string binaria de entrada dada. 

La máquina Mealy requerida se construye a continuación: 
 

Explicación: 
en el diagrama anterior, el estado inicial ‘X’ al obtener ‘1’ como entrada, permanece en el estado de sí mismo e imprime ‘0’ como salida y al obtener ‘0’ como entrada transmite a un estado ‘Y’ e imprime ‘1’ como salida y así sucesivamente para los estados restantes. 

Por ejemplo, cuando la string de entrada es ‘101’, la máquina de Moore arriba produce una salida como ‘010’, que no es más que el complemento a 1 de la entrada dada, es decir, 1 se convierte en 0 y viceversa. 
Por lo tanto, finalmente, la máquina Mealy anterior puede producir fácilmente el complemento de 1 de la string binaria de entrada dada. 

Conversión de máquina de Moore a máquina de Mealy: 
Diagrama de transición de estado de una máquina de Moore: 
 

Arriba, la máquina de Moore toma el número binario {0, 1} como entrada y produce el complemento a 1 de ese número como salida. 
Aquí se supone que la string de entrada se lee desde LSB (bit menos significativo) y se descarta el acarreo final. 

Ahora necesitamos transformar el diagrama de transición anterior de la máquina de Moore en el diagrama de transición de la máquina Mealy equivalente. Los pasos para la conversión requerida se dan a continuación: 

• Paso 1: Formación de la tabla de transición de estado de la máquina de Moore anterior. 
   

• En la tabla de transición anterior, los estados ‘X’ e ‘Y’ se mantienen en la primera columna que, al obtener ‘0’ como entrada, transita a los estados ‘Y’ e ‘Y’ respectivamente, se mantienen en la segunda columna y al obtener ‘1’ como entrada transita a los estados ‘X’ y ‘X’ respectivamente, mantenidos en la tercera columna y en la cuarta columna bajo Δ, hay salidas correspondientes de los estados de la primera columna. En la tabla, una flecha (→) indica el estado inicial. 

   

• Paso 2: Formación de la tabla de transición para la máquina Mealy desde arriba Tabla de transición de la máquina Moore 
  : la tabla de transición a continuación se formará con la ayuda de la tabla anterior y sus entradas simplemente usando la salida correspondiente de los estados de la primera columna y colocándolos en la segunda y tercera columna según corresponda. 
   

• En la tabla anterior, los estados en la primera columna como ‘X’ al obtener ‘0’ como entrada, pasa al estado ‘Y’ y da ‘1’ como salida y al obtener ‘1’ como entrada. al estado ‘X’ y da ‘0’ como salida y así sucesivamente para los estados restantes en la primera columna. En la tabla, una flecha (→) indica el estado inicial. 

   

• Paso 3: Finalmente, podemos formar el diagrama de transición de estado de la máquina Mealy con la ayuda de la tabla de transición anterior. 
  El diagrama requerido se muestra a continuación: 
   

• La máquina Mealy anterior toma el número binario {0, 1} como entrada y produce el complemento a 1 de ese número como salida. 
  Aquí se supone que la string de entrada se lee desde LSB (bit menos significativo) y se descarta el acarreo final. 

   

Nota: Al convertir de máquina Moore a Mealy, el número de estados sigue siendo el mismo para la máquina Moore y Mealy, pero en el caso de la conversión de Mealy a Moore, no da el mismo número de estados.