La forma más sencilla de demostrar que dos FSM son equivalentes es minimizar ambos y ver si los resultados son los mismos.
Para hacer esto, puede usar el procedimiento de minimización de partición como se explica en la sección 8.6.1 de Fundamentos de la lógica digital .
Sin entrar en demasiados detalles, ilustraré este procedimiento para su máquina de estado izquierda. La idea es particionar todos los estados de tal manera que los estados en la misma partición sean equivalentes.
Comenzamos suponiendo que todos los estados pueden ser equivalentes al dividir los estados en una partición. Antes de hacer esto, tenga en cuenta que los estados B y F son inalcanzables y se pueden eliminar del FSM. Por lo tanto, la primera partición es la siguiente:
$$ P_1 = (ACDE) $$
El siguiente paso es crear grupos de estados con el mismo valor de salida. Esto le da la siguiente partición:
$$ P_2 = (ACE) (D) $$
A continuación, debemos asegurarnos de que todos los 0-sucesores de los estados de un grupo estén contenidos en un grupo (lo mismo se aplica a los 1-sucesores). Por ejemplo, los sucesores 0 de (ACE) son (DAA) que no están contenidos en un solo grupo. Por lo tanto, el grupo (ACE) debe dividirse:
$$ P_3 = (A) (CE) (D) $$
Dado que tanto los sucesores 0 (AA) como los sucesores 1 (EC) de (CE) están contenidos dentro de un grupo, esta partición ya no necesita ser dividida. Esta partición final nos enseña que los estados C y E son equivalentes y necesitamos tres estados en el FSM mínimo.
Ahora podemos introducir nombres para los nuevos estados: S1 = (A), S2 = (CE) y S3 = (D) y construir una nueva tabla de estado:
-------------------------
Current Next state Output
State 0 1
-------------------------
S1 S3 S2 0
S2 S1 S2 0
S3 S2 S1 1
-------------------------
Al hacer lo mismo con la máquina de estado correcta, se obtiene la siguiente partición:
$$ P = (ACE) (D) (BF) $$
Al usar la asignación de estado S1 = (ACE), S2 = (D) y S3 = (BF) se obtiene exactamente la misma tabla de estados que la anterior. Por lo tanto, las dos máquinas de estado son equivalentes.
$$ \ blacksquare $$
