Minimización de AFD

Dificultad
Promedio 50%

Minimización de AFD

Teorema de Myhill-Nerode (minimización de un AFD). Sea L un lenguaje racional. Entre todos los AFD que reconocen L, hay uno y solo uno que tiene un número mínimo de estados.

Antes de minimizar un AFD, debe completarse, es decir, agregar un estado de basura como el estado R en el diagrama a continuación.

minimización de una AFD

El algoritmo de minimización es el siguiente:

  1. Completa el AFD llamado D
  2. Construya una partición inicial ∏ que contenga dos conjuntos I y II de estados tales que ∏ = {I = (estados de aceptación terminal de D), II = (otros estados de D)}
  3. Para cada estado de D hacer
    1. Construye la mesa de transición
    2. Marque los estados de salida y llegada según su grupo de ∏
  4. Si los estados del mismo grupo de ∏ tienen comportamientos divergentes
    1. Separe los estados en un nuevo grupo (III por ejemplo); preferiblemente haga solo una separación por iteración.
    2. Regresar a 3
  5. Fin: los nuevos estados son los grupos de ∏

Ejemplo

Tomemos el ejemplo de AFD anterior. De hecho, es determinista como se muestra en la tabla de transición.

Veamos la tabla de transición en el paso 3:

 ParaBvs
0 (yo)2 (II)5 (II)R (yo)
2 (II)R (yo)R (yo)R (yo)
5 (II)R (yo)R (yo)8 (II)
8 (II)R (yo)R (yo)8 (II)
R (yo)R (yo)R (yo)R (yo)

Notamos cuando en el grupo I, el comportamiento de O y R divergen, por lo tanto los separaremos en dos grupos: I = (0) y III = (R)

Aquí está la nueva tabla de transición:

 ParaBvs
0 (yo)2 (II)5 (II)R (III)
2 (II)R (III)R (III)R (III)
5 (II)R (III)R (III)8 (II)
8 (II)R (III)R (III)8 (II)
R (III)R (III)R (III)R (III)

Notamos que cuando en el grupo II, el comportamiento de 2 y 5, 8 divergen, los separaremos en dos grupos: II = (5, 8) y IV = (2)

Aquí está la nueva tabla de transición:

 ParaBvs
0 (yo)2 (IV)5 (II)R (III)
2 (IV)R (III)R (III)R (III)
5 (II)R (III)R (III)8 (II)
8 (II)R (III)R (III)8 (II)
R (III)R (III)R (III)R (III)

Ya no observamos ninguna divergencia entre los grupos, por lo que podemos realizar la tabla de transición con AFD minimizado dando la siguiente tabla de transición:

 ParaBvs
IIVIIIII
IVIIIIIIIII
IIIIIIIIII
IIIIIIIIIIII

El estado inicial es I (en relación con su equivalente en D), y los estados terminales del autómata son II y IV (en relación con sus equivalentes en D).

Otro ejemplo

Considere el siguiente autómata:

minimización de una AFD

La fase de inicialización permite obtener el grupo no terminal I y el grupo terminal II:

 PARABVSD
En esoIIIIII

Veamos las transiciones para cada estado según los grupos I y II:

AlfabetoPARABVSD
ParaIIIIIII
OIIIIII

Luego realizamos la separación de conjuntos. Dos estados están en el mismo conjunto si ya estaban en el mismo conjunto y si las transiciones conducen a los mismos conjuntos. En este ejemplo, B y D se comportan exactamente de la misma manera, por lo que permanecen juntos. Por otro lado, A y C que formaban parte del mismo conjunto se comportan de manera diferente en el símbolo "a". En consecuencia, el conjunto anotado I se divide en dos. Entonces obtenemos:

 PARABVSD
En esoIIIIII
ParaIIIIIII
0IIIIII
Separación 1IIIIIIII

La situación actual (la línea del Balance 1) es diferente a la situación inicial. Entonces tenemos que empezar de nuevo.

 PARABVSD
En esoIIIIII
ParaIIIIIII
0IIIIII
Separación 1IIIIIIII
PARAIIIIIIIII
0IIIIIIIIII
Separación 2IIIIIIII

La línea "Separación 2" es idéntica a la línea "Separación 1". En consecuencia, en cada uno de los conjuntos restantes, los estados no son distinguibles (se comportan exactamente de la misma manera y, por lo tanto, son "redundantes").

Para que podamos construir el nuevo autómata asociando un estado a cada conjunto. Las transiciones se indican en la tabla. El estado inicial es el que contiene el estado inicial del autómata de partida: aquí I contiene el estado A, estado inicial. Los estados finales son los estados cuyo conjunto correspondiente contiene al menos un estado final: aquí, II contiene B y D que son finales.

minimización de una AFD

Hasta ahora, hemos "fusionado" los estados indistinguibles. Ahora debe eliminar todos los estados innecesarios restantes. En nuestro ejemplo, el estado III es un estado estéril (no terminal y sin transición), por lo tanto, inútil. Por tanto, debe suprimirse. De ahí el autómata determinista mínimo de la siguiente figura:

minimización de una AFD
Compartir, repartir