Minimización de un 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 basura como el estado R en el diagrama a continuación.
El algoritmo de minimización es el siguiente:
- Complete el AFD denominado D
- Construya una partición inicial ∏ que contenga dos conjuntos I y II de estados tales que ∏={I=(terminar estados de aceptación de D), II=(otros estados estados de D)}
- Para cada estado de D hacer
- Construye la mesa de transición
- Marque los estados de salida y llegada según su grupo de ∏
- Si los estados del mismo grupo de ∏ tienen comportamientos divergentes
- Separe los estados en un nuevo grupo (III por ejemplo), preferiblemente solo haga una separación por iteración.
- Regresar a 3
- Fin: los nuevos estados son los grupos de ∏
Ejemplo
Volvamos al ejemplo anterior de AFD. De hecho, es determinista como se muestra en la tabla de transición.
Veamos la tabla de transición en el paso 3:
| Para | B | vs | |
| 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:
| Para | B | vs | |
| 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:
| Para | B | vs | |
| 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 el DFA minimizado dando la siguiente tabla de transición:
| Para | B | vs | |
| I | IV | II | III |
| IV | III | III | III |
| II | III | III | II |
| III | III | III | III |
El estado inicial es I (en relación a su equivalente en D), y los estados terminales del autómata son II y IV (en relación a sus equivalentes en D).
Otro ejemplo
Considere el siguiente autómata:
La fase de inicialización permite obtener el grupo no terminal I y el grupo terminal II:
| PARA | B | VS | D | |
| En eso | I | II | I | II |
Veamos las transiciones para cada estado según los grupos I y II:
| Alfabeto | PARA | B | VS | D |
| Para | II | II | I | II |
| O | I | II | I | II |
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:
| PARA | B | VS | D | |
| En eso | I | II | I | II |
| Para | II | II | I | II |
| 0 | I | II | I | II |
| Separación 1 | I | II | III | II |
La situación actual (la línea del Balance 1) es diferente a la situación inicial. Entonces tenemos que empezar de nuevo.
| PARA | B | VS | D | |
| En eso | I | II | I | II |
| Para | II | II | I | II |
| 0 | I | II | I | II |
| Separación 1 | I | II | III | II |
| PARA | II | II | III | II |
| 0 | III | II | III | II |
| Separación 2 | I | II | III | II |
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.
Por ahora, hemos "fusionado" los estados indistinguibles. Ahora es necesario eliminar todos los estados inútiles restantes. En nuestro ejemplo, el estado III es un estado estéril (no terminal y sin transición), por lo tanto inútil. Por lo tanto, debe ser eliminado. De ahí el autómata determinista mínimo de la siguiente figura:
