Contenido
PalancaMinimizació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.
El algoritmo de minimización es el siguiente:
- Completa el AFD llamado D
- 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)}
- 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 haga solo una separación por iteración.
- Regresar a 3
- 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:
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 AFD 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 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:
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.
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: