Equivalencia de FSA (autómatas de estado finito)

Un autómata es una máquina que tiene un número finito de estados. Cualquier dos autómatas se dice que es equivalente si ambos aceptan exactamente el mismo conjunto de strings de entrada. 
Dos autómatas son equivalentes si cumplen las siguientes condiciones: 

1. Los estados inicial y final de ambos autómatas deben ser iguales.
2. Cada par de estados elegidos es solo de un autómata diferente.
3. Al combinar los estados con los alfabetos de entrada, los resultados del par deben ser estados finales o estados intermedios (es decir, ambos deben estar en el estado final o en el estado no final).
4. Si el par resultante tiene diferentes tipos de estados, entonces será no equivalente. (es decir, uno se encuentra en el estado final y el otro se encuentra en el estado intermedio).

Ejemplo 1:
considere dos autómatas diferentes que se muestran a continuación en la Figura 1.

Solución –
Paso 1 – Dado que los estados inicial y final de ambos autómatas son los mismos, entonces se verifica.
Paso 2: verifique cada estado haciendo una tabla de estados con respecto a los alfabetos de entrada.

Aquí,
FS representa -> Estado final.
IS representa -> Estado intermedio (Estado no final) .

Paso 3: para cada par de estados, los estados resultantes se encuentran en FS o en IS como una combinación.

Conclusión: ambos autómatas son equivalentes.

Nota: si el par de estados resultante tiene una combinación diferente de estados (es decir, (FS, IS) o (IS, FS), se dice que ambos autómatas no son equivalentes.

Ejemplo 2:
considere dos autómatas diferentes que se muestran a continuación en la Figura 2.

Solución –
Paso 1 – Dado que los estados inicial y final de ambos autómatas son los mismos, se verifica.
Paso 2: verifique cada estado haciendo una tabla de estados con respecto a los alfabetos de entrada.

Aquí,
FS representa -> Estado final.
IS representa -> Estado intermedio (Estado no final) .
Paso 3: para el primer par de estados, los estados resultantes se encuentran en FS como una combinación 
. Paso 4: pero para el par (q2, q5), cuando se opera sobre alfabetos de entrada, se encuentran en diferentes estados. (es decir, uno en FS y el otro en IS).

Conclusión: los autómatas dados no son equivalentes.

Ejemplo 3:
considere dos autómatas diferentes que se muestran a continuación en la Figura 3.

Solución –
Paso 1 – Dado que los estados inicial y final de ambos autómatas son los mismos, se verifica.
Paso 2: verifique cada estado haciendo una tabla de estados con respecto a los alfabetos de entrada.

Aquí,
FS representa -> Estado final.
IS representa -> Estado intermedio (Estado no final) .
Paso 3: para el par (q1, q3), cuando se opera sobre alfabetos de entrada, se encuentran en diferentes estados. (es decir, uno en FS y el otro en IS).

Conclusión: los autómatas dados no son equivalentes.

Ejemplo 4:
considere dos autómatas diferentes que se muestran a continuación en la Figura 4.

Solución –
Paso 1 – Dado que los estados inicial y final de ambos autómatas son los mismos, entonces se verifica.
Paso 2: verifique cada estado haciendo una tabla de estados con respecto a los alfabetos de entrada .

Aquí,
FS representa -> Estado final.
IS representa -> Estado intermedio (Estado no final) .
Paso 3: para cada par de estados, los estados resultantes se encuentran en FS o en IS como una combinación.

Conclusión: ambos autómatas son equivalentes.