En la teoría de autómatas (una rama de la informática teórica ), la minimización de DFA es la tarea de transformar un autómata finito determinista (DFA) dado en un DFA equivalente que tenga un número mínimo de estados. Aquí, dos DFA se denominan equivalentes si reconocen el mismo lenguaje regular . Se conocen varios algoritmos diferentes que realizan esta tarea y se describen en los libros de texto estándar sobre teoría de autómatas. [1]
Para cada lenguaje regular, también existe un autómata mínimo que lo acepta, es decir, un DFA con un número mínimo de estados y este DFA es único (excepto que a los estados se les pueden dar nombres diferentes). [2] [3] El DFA mínimo asegura un costo computacional mínimo para tareas como la coincidencia de patrones .
Hay tres clases de estados que se pueden eliminar o fusionar del DFA original sin afectar el lenguaje que acepta.
La minimización de DFA generalmente se realiza en tres pasos:
El estado de un autómata finito determinista es inalcanzable si no existe ninguna cadena en para la que . En esta definición, es el conjunto de estados, es el conjunto de símbolos de entrada, es la función de transición (que asigna un estado y un símbolo de entrada a un conjunto de estados), es su extensión a cadenas (también conocida como función de transición extendida), es el estado inicial y es el conjunto de estados de aceptación (también conocidos como finales). Los estados alcanzables se pueden obtener con el siguiente algoritmo:
deje que estados_alcanzables := { q0 } deje que nuevos_estados := { q0 }do { temp := el conjunto vacío para cada q en nuevos_estados do para cada c en Σ do temp := temp ∪ { δ ( q , c )} nuevos_estados := temp \ estados_alcanzables estados_alcanzables := estados_alcanzables ∪ nuevos_estados } while ( nuevos_estados ≠ el conjunto vacío ) estados_inalcanzables := Q \ estados_alcanzablesSuponiendo una implementación eficiente de los conjuntos de estados (por ejemplo, new_states) y operaciones sobre ellos (como agregar un estado o verificar si está presente), este algoritmo se puede implementar con una complejidad de tiempo , donde es el número de estados y es el número de transiciones del autómata de entrada.
Los estados inalcanzables se pueden eliminar del DFA sin afectar el idioma que acepta.
Los siguientes algoritmos presentan varios enfoques para fusionar estados no distinguibles.
Un algoritmo para fusionar los estados no distinguibles de un DFA, debido a Hopcroft (1971), se basa en el refinamiento de partición , dividiendo los estados del DFA en grupos según su comportamiento. Estos grupos representan clases de equivalencia de la congruencia de Nerode , por la cual cada dos estados son equivalentes si tienen el mismo comportamiento para cada secuencia de entrada. Es decir, para cada dos estados p 1 y p 2 que pertenecen al mismo bloque de la partición P , y cada palabra de entrada w , las transiciones determinadas por w siempre deben llevar a los estados p 1 y p 2 a estados que ambos aceptan o a estados que ambos rechazan. No debería ser posible que w lleve a p 1 a un estado de aceptación y a p 2 a un estado de rechazo o viceversa.
El siguiente pseudocódigo describe la forma del algoritmo tal como lo propuso Xu. [4] También se han presentado formas alternativas. [5] [6]
P := { F , Q \ F } W := { F , Q \ F }mientras ( W no está vacío ) elija y elimine un conjunto A de W para cada c en Σ sea X el conjunto de estados para los cuales una transición en c conduce a un estado en A para cada conjunto Y en P para el cual X ∩ Y no está vacío e Y \ X no está vacío reemplace Y en P por los dos conjuntos X ∩ Y e Y \ X si Y está en W reemplace Y en W por los mismos dos conjuntos de lo contrario si | X ∩ Y | <= | Y \ X | agregue X ∩ Y a W de lo contrario agregue Y \ X a W El algoritmo comienza con una partición demasiado burda: cada par de estados que son equivalentes según la congruencia de Nerode pertenece al mismo conjunto en la partición, pero los pares que no son equivalentes también pueden pertenecer al mismo conjunto. Gradualmente refina la partición en un número mayor de conjuntos más pequeños, dividiendo en cada paso los conjuntos de estados en pares de subconjuntos que son necesariamente no equivalentes. La partición inicial es una separación de los estados en dos subconjuntos de estados que claramente no tienen el mismo comportamiento entre sí: los estados de aceptación y los estados de rechazo. Luego, el algoritmo elige repetidamente un conjunto A de la partición actual y un símbolo de entrada c , y divide cada uno de los conjuntos de la partición en dos subconjuntos (posiblemente vacíos): el subconjunto de estados que conducen a A en el símbolo de entrada c , y el subconjunto de estados que no conducen a A . Dado que ya se sabe que A tiene un comportamiento diferente al de los otros conjuntos de la partición, los subconjuntos que conducen a A también tienen un comportamiento diferente al de los subconjuntos que no conducen a A . Cuando no se pueden encontrar más divisiones de este tipo, el algoritmo finaliza.
Lema . Dado un carácter fijo c y una clase de equivalencia Y que se divide en clases de equivalencia B y C , solo una de B o C es necesaria para refinar toda la partición. [7]
Ejemplo: Supongamos que tenemos una clase de equivalencia Y que se divide en las clases de equivalencia B y C . Supongamos que también tenemos las clases D , E y F ; D y E tienen estados con transiciones a B en el carácter c , mientras que F tiene transiciones a C en el carácter c . Por el Lema, podemos elegir B o C como el diferenciador, digamos B . Entonces los estados de D y E se dividen por sus transiciones a B . Pero F , que no apunta a B , simplemente no se divide durante la iteración actual del algoritmo; será refinada por otro(s) diferenciador(es).
Observación . Se necesitan todos los valores de B o C para dividir correctamente las clases de referencia como D , E y F (los subconjuntos no sirven).
El propósito de la ifdeclaración más externa ( if Y is in W) es parchar W , el conjunto de diferenciadores. Vemos en la declaración anterior en el algoritmo que Y acaba de ser dividido. Si Y está en W , simplemente se ha vuelto obsoleto como un medio para dividir clases en iteraciones futuras. Entonces Y debe ser reemplazado por ambas divisiones debido a la Observación anterior. Sin embargo, si Y no está en W , solo una de las dos divisiones, no ambas, necesita agregarse a W debido al Lema anterior. Elegir la más pequeña de las dos divisiones garantiza que la nueva adición a W no sea más que la mitad del tamaño de Y ; este es el núcleo del algoritmo de Hopcroft: cómo obtiene su velocidad, como se explica en el siguiente párrafo.
El tiempo de ejecución en el peor de los casos de este algoritmo es O ( ns log n ) , donde n es el número de estados y s es el tamaño del alfabeto. Este límite se deriva del hecho de que, para cada una de las ns transiciones del autómata, los conjuntos extraídos de Q que contienen el estado objetivo de la transición tienen tamaños que disminuyen entre sí por un factor de dos o más, por lo que cada transición participa en O (log n ) de los pasos de división en el algoritmo. La estructura de datos de refinamiento de partición permite que cada paso de división se realice en un tiempo proporcional al número de transiciones que participan en él. [8] Este sigue siendo el algoritmo más eficiente conocido para resolver el problema, y para ciertas distribuciones de entradas su complejidad de caso promedio es incluso mejor, O ( n log log n ) . [6]
Una vez que se ha utilizado el algoritmo de Hopcroft para agrupar los estados del DFA de entrada en clases de equivalencia, el DFA mínimo se puede construir formando un estado para cada clase de equivalencia. Si S es un conjunto de estados en P , s es un estado en S y c es un carácter de entrada, entonces la transición en el DFA mínimo desde el estado para S , en la entrada c , va al conjunto que contiene el estado al que iría el autómata de entrada desde el estado s en la entrada c . El estado inicial del DFA mínimo es el que contiene el estado inicial del DFA de entrada, y los estados aceptantes del DFA mínimo son aquellos cuyos miembros son estados aceptantes del DFA de entrada.
El algoritmo de Moore para la minimización de DFA se debe a Edward F. Moore (1956). Al igual que el algoritmo de Hopcroft, mantiene una partición que comienza separando los estados de aceptación de los de rechazo, y refina repetidamente la partición hasta que no se pueden hacer más refinamientos. En cada paso, reemplaza la partición actual con el refinamiento común más grueso de s + 1 particiones, una de las cuales es la actual y el resto son las preimágenes de la partición actual bajo las funciones de transición para cada uno de los símbolos de entrada. El algoritmo termina cuando este reemplazo no cambia la partición actual. Su complejidad temporal en el peor de los casos es O ( n 2 s ) : cada paso del algoritmo puede realizarse en tiempo O ( ns ) utilizando una variante de ordenación por radix para reordenar los estados de modo que los estados en el mismo conjunto de la nueva partición sean consecutivos en el ordenamiento, y hay como máximo n pasos ya que cada uno excepto el último aumenta el número de conjuntos en la partición. Las instancias del problema de minimización de DFA que causan el comportamiento en el peor de los casos son las mismas que para el algoritmo de Hopcroft. El número de pasos que realiza el algoritmo puede ser mucho menor que n , por lo que en promedio (para s constante ) su rendimiento es O ( n log n ) o incluso O ( n log log n ) dependiendo de la distribución aleatoria de autómatas elegida para modelar el comportamiento en el caso promedio del algoritmo. [6] [9]
La inversión de las transiciones de un autómata finito no determinista (AFN) y la alternancia de los estados inicial y final [nota 1] produce un AFN para la inversión del lenguaje original. La conversión de este AFN en un AFD utilizando la construcción estándar de conjuntos de potencias (manteniendo solo los estados alcanzables del AFD convertido) conduce a un AFD para el mismo lenguaje invertido. Como observó Brzozowski (1963), la repetición de esta inversión y determinización una segunda vez, nuevamente manteniendo solo los estados alcanzables, produce el AFD mínimo para el lenguaje original.
La intuición detrás del algoritmo es la siguiente: al determinar el autómata inverso se fusionan estados que no son distinguibles en el autómata original, pero pueden producirse varios estados de aceptación. En tal caso, cuando invertimos el autómata por segunda vez, estos estados de aceptación se vuelven iniciales y, por lo tanto, el autómata no será determinista debido a que tiene múltiples estados iniciales. Es por eso que necesitamos determinarlo nuevamente, obteniendo el DFA mínimo.
Después de que determinamos para obtener , invertimos esto para obtener . Ahora reconoce el mismo lenguaje que , pero hay una diferencia importante: no hay dos estados en desde los cuales podamos aceptar la misma palabra. Esto se deduce de ser determinista, es decir, no hay dos estados en a los que podamos llegar desde el estado inicial a través de la misma palabra. La determinización de entonces crea estados de potencia (conjuntos de estados de ), donde cada dos estados de potencia difieren ‒naturalmente‒ en al menos un estado de . Supongamos que y ; entonces contribuye con al menos una palabra [nota 2] al lenguaje de , [nota 3] que posiblemente no podría estar presente en , ya que esta palabra es única para (ningún otro estado la acepta). Vemos que esto se cumple para cada par de estados de potencia, y por lo tanto cada estado de potencia es distinguible de cualquier otro estado de potencia. Por lo tanto, después de la determinación de , tenemos un DFA sin estados indistinguibles o inalcanzables; por lo tanto, el DFA mínimo para el original .
La complejidad del peor caso del algoritmo de Brzozowski es exponencial en el número de estados del autómata de entrada. Esto se cumple independientemente de si la entrada es un NFA o un DFA. En el caso del DFA, la explosión exponencial puede ocurrir durante la determinación de la inversión del autómata de entrada; [nota 4] en el caso del NFA, también puede ocurrir durante la determinación inicial del autómata de entrada. [nota 5] Sin embargo, el algoritmo con frecuencia funciona mejor de lo que sugeriría este peor caso. [6]
Si bien los procedimientos anteriores funcionan para los DFA, el método de partición no funciona para los autómatas finitos no deterministas (NFA). [10] Si bien una búsqueda exhaustiva puede minimizar un NFA, no existe un algoritmo de tiempo polinomial para minimizar los NFA generales a menos que P = PSPACE , una conjetura sin resolver en la teoría de la complejidad computacional que se cree ampliamente que es falsa. Sin embargo, existen métodos de minimización de NFA que pueden ser más eficientes que la búsqueda de fuerza bruta. [11]
{{cite web}}: Falta o está vacío |url=( ayuda )