Diseño de autómatas finitos para varias operaciones como complemento a 1, complemento a 2

Transductores en autómatas finitos (FA) significa FA con salida.
Hay dos tipos de Máquinas para FA con Salida.

1. Mealy Machine: 
Es la FA en la que se asocia la salida a cada transición. (Eso significa que la salida depende del estado y la entrada).
2. Máquina de Moore: 
Es una FA en la que se asocia la salida a cada estado. (Eso significa que la salida depende solo del estado).

Al usar estas máquinas, podemos diseñar autómatas finitos para varias operaciones como:

• Complemento a 1.
• Complemento a 2.
• Sumador completo binario.
• Incrementar en 1.
• Cambia el bit de signo.
• Probador de divisibilidad de enteros.
• Funciones lógicas (XOR, OR, AND, NOT).
• Suma del bit actual y del bit anterior, etc.

1. Complemento a 1: 

El complemento a 1 de un número binario dado se obtiene simplemente invirtiendo cada bit. 
es decir, 1 <–> 0 y 0 <–> 1

Lógica para diseñar usando Mealy Machine –

• Para la entrada 0, la salida es 1.
• Para la entrada 1, la salida es 0.
  Por lo tanto, solo requiere un estado.

2. Complemento a 2: 

Generalmente, el complemento a 2 se obtiene sumando 1 al complemento a 1 del número.
Pero para diseñar la máquina de complemento a 2, usamos otro algoritmo para derivar el complemento a 2.

Algoritmo –

• Comience desde LSB de la entrada.
• Copie el bit tal cual hasta que aparezca el primer ‘1’.
• Después de eso, complementa cada bit.

Ejemplo –

Lógica para diseñar usando Mealy Machine –

• Tome la entrada de LSB de la entrada.
• Para cada entrada hasta, la primera salida 1 es la misma que la entrada.
• Después de eso, para cada entrada, complemente cada bit usando la máquina de complemento a 1.

Por lo tanto, requiere 2 estados. Un estado donde la salida es la misma que la entrada y otro estado es el estado de complemento a 1.

Cuando llega el primer ‘1’, se transfiere al siguiente estado para hacer el complemento de cada bit.
Aquí, el comportamiento del primer estado es generar la misma salida que la entrada y el comportamiento del segundo estado es generar el complemento.

3. Sumador completo binario:
El sumador completo binario agrega 2 bits binarios y lleva la entrada y genera una salida de suma y una salida de acarreo.

Funcionamiento del sumador completo binario –

Esta es una tabla de funcionalidad del sumador completo binario. Dependiendo de la entrada de acarreo, el valor de salida de la entrada cambia.

Para diseñar un sumador binario completo, usamos esta tabla. Según esta tabla, hay dos casos (carry=0 y carry=1), por lo que necesitamos dos estados.

Cuando Carry=0 (Desde el estado Carry=0) En “00” ingrese Sum=0 (Entonces, en la transición 00 la salida es 0) y Carry=0 (Entonces, va al estado Carry=0)

Diseñe el resto de la máquina según la tabla. Parece que –

4. Incrementar en 1:
Incrementar en 1 significa agregar 1 al número binario.
Hay dos casos en incremento por 1 operación

Lógica para el diseño de máquinas –

Al combinar ambos casos, obtuvimos el algoritmo que, hasta que sale el primer 0, hace todo 1 ⇢ 0 y cuando sale 0 lo hace 1, entonces la parte restante de la salida es igual a la entrada. Aquí, las entradas se toman de LSB.

5. Cambie el bit de signo:

Cambiar el bit de signo es muy simple. Simplemente intercambie el primer bit y los otros bits son iguales.

6. Probador de divisibilidad entera:

La máquina de prueba de divisibilidad de enteros es lo mismo que una máquina de modulación, aceptando el valor decimal con salida en el estado.

Ejemplo: 
la máquina de prueba de 3 divisibilidades es lo mismo que los autómatas finitos para el valor decimal de la string mod 3 = 0 con salida en el estado

7. Funciones lógicas (XOR, OR, AND, NOT):

Es muy fácil diseñar máquinas para funciones lógicas basadas en sus tablas lógicas.

8. Suma del bit actual y del bit anterior:

Si bit anterior = 0, en entrada 0, salida = 00 y en entrada 1, salida = 01 
Si bit anterior = 1, en entrada 0, salida = 01 y en entrada 1, salida = 10

En pre=0, cuando hay una transición de 1, se mueve a pre=1 porque tiene que ir al bit anterior para el bit siguiente. Lo mismo ocurre en el caso de transición 0 en pre=1