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 tiene un número mínimo de estados. Aquí, dos DFA se denominan equivalentes si reconocen el mismo idioma regular . En los libros de texto estándar sobre teoría de autómatas se conocen y describen varios algoritmos diferentes que logran esta tarea. [1]
DFA mínimo
Para cada idioma 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 los estados pueden tener diferentes nombres). [2] [3] El DFA mínimo asegura un costo computacional mínimo para tareas como la coincidencia de patrones .
Hay dos clases de estados que se pueden eliminar o fusionar del DFA original sin afectar el idioma que acepta para minimizarlo.
- Los estados inalcanzables son los estados a los que no se puede acceder desde el estado inicial del DFA, para cualquier cadena de entrada.
- Los estados no distinguibles son aquellos que no se pueden distinguir entre sí para ninguna cadena de entrada.
La minimización de DFA generalmente se realiza en tres pasos, correspondientes a la eliminación o fusión de los estados relevantes. Dado que la eliminación de estados no distinguibles es computacionalmente la más costosa, generalmente se realiza como último paso.
Estados inalcanzables
El estado de un autómata finito determinista es inalcanzable si no hay cuerda en existe para lo cual . En esta definición, es el conjunto de estados, es el conjunto de símbolos de entrada, es la función de transición (mapeando 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:
let reachable_states : = { q0 }; let new_states : = { q0 };do { temp : = el conjunto vacío ; para cada q en new_states hacer para cada c en Σ do temp : = temp ∪ { p tal que p = δ ( q , c )}; terminar ; terminar ; new_states : = temp \ reachable_states ; reachable_states : = reachable_states ∪ new_states ; } while ( new_states ≠ el conjunto vacío ); unreachable_states : = Q \ reachable_states ;
Los estados inalcanzables se pueden eliminar de DFA sin afectar el idioma que acepta.
Estados no distinguibles
Algoritmo de Hopcroft
Un algoritmo para fusionar los estados no distinguibles de un DFA, debido a Hopcroft (1971) , se basa en el refinamiento de la partición, dividiendo los estados del DFA en grupos según su comportamiento. Estos grupos representan clases de equivalencia de la relación de equivalencia Myhill-Nerode , en la que cada dos estados de la misma partición son equivalentes si tienen el mismo comportamiento para todas las secuencias de entrada. Es decir, para cada dos estados p 1 y p 2 que pertenecen a la misma clase de equivalencia dentro de la partición P , y cada palabra de entrada w , las transiciones determinadas por w siempre deben tomar los estados p 1 y p 2 a estados iguales, establece que ambos aceptan, o declaran que ambos rechazan. No debería ser posible que w lleve p 1 a un estado de aceptación y p 2 a un estado de rechazo o viceversa.
El siguiente pseudocódigo describe el algoritmo:
P : = { F , Q \ F }; W : = { F , Q \ F }; mientras que ( W es no vacío ) no elegir y eliminar un conjunto A de W para cada c en Σ no deje que X sea el conjunto de estados para que una transición en c conduce a un estado en A para cada conjunto Y en P para que X ∩ y es no vacío y y \ X es no vacío no reemplazar y en P por los dos conjuntos X ∩ y y y \ X si y está en W reemplazar y en W por los mismos dos conjuntos demás si | X ∩ Y | <= | Y \ X | agregue X ∩ Y a W; de lo contrario, agregue Y \ X al extremo W ; terminar ; terminar ;
El algoritmo comienza con una partición que es demasiado burda: cada par de estados que son equivalentes según la relación Myhill-Nerode pertenecen 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 conjuntos de estados en pares de subconjuntos que son necesariamente desiguales. 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 una . Desde A ya se sabe que 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 de los subconjuntos que no conducen a una . Cuando no se pueden encontrar más divisiones de este tipo, el algoritmo termina.
Lema . Dado un carácter fijo cy una clase de equivalencia Y que se divide en clases de equivalencia B y C, solo uno de B o C es necesario para refinar toda la partición. [4]
Ejemplo: supongamos que tenemos una clase de equivalencia Y que se divide en 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. Según el lema, podemos elegir B o C como distintivo, 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á refinado por otros distinguidores.
Observación . Todo B o C es necesario para dividir clases de referencia como D, E y F correctamente; los subconjuntos no sirven.
El propósito de la declaración if más externa ( si Y está en W ) es parchear W, el conjunto de distintivos. Vemos en la declaración anterior en el algoritmo que Y acaba de dividirse. 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, debe agregarse a W debido al Lema anterior. La elección de la más pequeña de las dos divisiones garantiza que la nueva adición a W no sea más de 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 peor tiempo de ejecución 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í en 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 la partición permite que cada paso de división se realice en un tiempo proporcional al número de transiciones que participan en él. [5] Este sigue siendo el algoritmo más eficiente conocido para resolver el problema, y para ciertas distribuciones de entradas su complejidad promedio de casos 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 en el que el el autómata de entrada iría 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 de aceptación del DFA mínimo son aquellos cuyos miembros están aceptando estados del DFA de entrada.
Algoritmo de Moore
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 y rechazo, y refina repetidamente la partición hasta que no se pueden realizar más refinamientos. En cada paso, reemplaza la partición actual con el refinamiento común más grueso de las particiones s + 1 , una de las cuales es la actual y las otras son las imágenes previas 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 de tiempo en el peor de los casos es O ( n 2 s ) : cada paso del algoritmo se puede realizar en el tiempo O ( ns ) usando una variante de ordenación de base para reordenar los estados de modo que los estados en el mismo conjunto de la nueva partición sean consecutivos en el orden, 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 provocan el peor comportamiento 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 constantes ) su rendimiento es O ( n log n ) o incluso O ( n log log n ) dependiendo de la distribución aleatoria de los autómatas elegidos para modelar el comportamiento de caso promedio del algoritmo. [6] [7]
El algoritmo de Brzozowski
Invertir las transiciones de un autómata finito no determinista (NFA)y cambiar los estados inicial y final [nota 1] produce un NFApara la inversión del idioma original. La conversión de este NFA en un DFA utilizando la construcción estándar de powerset (manteniendo solo los estados alcanzables del DFA convertido) conduce a un DFApara el mismo idioma invertido. Como observó Brzozowski (1963) , la repetición de esta inversión y determinación por segunda vez, manteniendo nuevamente solo estados alcanzables, produce el DFA mínimo para el idioma original.
La intuición detrás del algoritmo es la siguiente: después de determinar para obtener , revertimos esto para obtener . Ahora tiene el mismo idioma que , pero hay una diferencia importante: no hay dos estados en del cual podemos aceptar la misma palabra. Esto se sigue deser determinista, a saber. no hay dos estados en, al que podemos llegar desde el estado inicial a través de la misma palabra. La determinación de luego crea estados de poder (conjuntos de estados de ), donde cada dos estados de potencia difieren - naturalmente - en al menos un estado de . Asumir y ; luegoaporta al menos una palabra [nota 2] al idioma de[nota 3] que posiblemente no podría estar presente en, ya que esta palabra es exclusiva de (ningún otro estado lo acepta). Vemos que esto es válido para cada par de estados de poder y, por lo tanto, cada estado de poder se distingue de todos los demás. 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 .
Si ya es determinista, entonces basta con recortarlo, [nota 4] revertirlo, determinarlo y luego revertirlo nuevamente. Podría pensarse que esto comienza conen el proceso anterior (asumiendo que ya se ha recortado), ya que la entrada FA ya es determinista (pero tenga en cuenta que en realidad no es una inversión). Revertimos y determinamos para obtener , que es el DFA mínimo para la inversión del idioma de(ya que solo hicimos una inversión hasta ahora). Ahora todo lo que queda por hacer es revertir para obtener el DFA mínimo para el idioma original.
La complejidad del peor de los casos del algoritmo de Brzozowski es exponencial en el número de estados del autómata de entrada. Esto es válido independientemente de si la entrada es un NFA o un DFA. En el caso de DFA, la explosión exponencial puede ocurrir durante la determinación de la inversión del autómata de entrada; [nota 5] en el caso de NFA, también puede suceder durante la determinación inicial del autómata de entrada. [nota 6] Sin embargo, el algoritmo funciona con frecuencia mejor de lo que sugeriría este peor de los casos. [6]
Minimización de NFA
Si bien los procedimientos anteriores funcionan para los DFA, el método de particionamiento no funciona para los autómatas finitos no deterministas (NFA). [8] 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 no resuelta en la teoría de la complejidad computacional que se cree que es falsa. Sin embargo, existen métodos de minimización de NFA que pueden ser más eficientes que la búsqueda por fuerza bruta. [9]
Ver también
Notas
- ^ Hopcroft, Motwani y Ullman (2001) , sección 4.4.3, "Minimización de DFA".
- ^ Hopcroft y Ullman (1979) , Sección 3.4, Teorema 3.10, p.67
- ^ Hopcroft, Motwani y Ullman (2001) , sección 4.4.3, "Minimización de DFA", p. 159 y pág. 164 (observación después del teorema 4.26)
- ^ Basado en el corolario 10 de Knuutila (2001)
- ^ Hopcroft (1971) ; Aho, Hopcroft y Ullman (1974)
- ^ a b c Berstel y col. (2010) .
- ^ David (2012) .
- ^ Hopcroft, Motwani & Ullman (2001) , Sección 4.4, Figura etiquetada "Minimizar los estados de una NFA", p. 163.
- ^ Kameda y Weiner (1970) .
- ^ En caso de que haya varios estados finales en M, debemos permitir múltiples estados iniciales en la inversión de M; o agregue un estado adicional con transiciones ε a todos los estados iniciales y haga que solo este nuevo estado sea inicial.
- ^ Recuerde que no hay estados muertos en M '; por lo tanto, se acepta al menos una palabra de cada estado.
- ^ El idioma de un estado es el conjunto de palabras aceptadas de ese estado.
- ^ Trim = eliminar estados inaccesibles y muertos.
- ^ Por ejemplo, el lenguaje de cadenas binarias cuyo n- ésimo símbolo es uno requiere solo n + 1 estados, pero su inversión requiere 2 n estados. Leiss (1981) proporciona unDFAternario de n estados cuya inversión requiere 2 n estados, el máximo posible. Para obtener ejemplos adicionales y la observación de la conexión entre estos ejemplos y el análisis del peor de los casos del algoritmo de Brzozowski, consulte Câmpeanu et al. (2001) .
- ^ La explosión exponencial ocurrirá como máximo una vez, no en ambas determinaciones. Es decir, el algoritmo es, en el peor de los casos, exponencial, no doblemente exponencial.
Referencias
- Aho, Alfred V .; Hopcroft, John E .; Ullman, Jeffrey D. (1974), "4.13 Particionamiento", El diseño y análisis de algoritmos informáticos , Addison-Wesley, págs. 157-162.
- Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimización de los autómatas", Autómatas: de las matemáticas a las aplicaciones , European Mathematical Society, arXiv : 1010.5318 , Bibcode : 2010arXiv1010.5318B
- Brzozowski, JA (1963), "Expresiones regulares canónicas y gráficos de estado mínimo para eventos definidos", Proc. Simpos. Matemáticas. Theory of Automata (Nueva York, 1962) , Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, NY, págs. 529–561, MR 0175719.
- Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", IV Taller internacional sobre implementación de autómatas (WIA '99) , Lecture Notes in Computer Science, 2214 , Springer-Verlag, págs. 60-70, doi : 10.1007 / 3-540-45526-4_6 , ISBN 978-3-540-42812-1.
- David, Julien (2012), "Complejidad promedio de los algoritmos de Moore y Hopcroft", Ciencias de la computación teóricas , 417 : 50–65, doi : 10.1016 / j.tcs.2011.10.011.
- Hopcroft, John (1971), "Un algoritmo n log n para minimizar estados en un autómata finito", Teoría de máquinas y cálculos (Proc. Internat. Sympos., Technion, Haifa, 1971) , Nueva York: Academic Press, págs. 189-196, SR. 0403320. Véase también la versión preliminar, Informe técnico STAN-CS-71-190 , Universidad de Stanford, Departamento de Ciencias de la Computación, enero de 1971.
- Hopcroft, John E .; Ullman, Jeffrey D. (1979), Introducción a la teoría, los lenguajes y la computación de los autómatas , Lectura / MA: Addison-Wesley, ISBN 978-0-201-02988-8
- Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2001), Introducción a la teoría, los lenguajes y la computación de los autómatas (2a ed.), Addison-Wesley.
- Kameda, Tsunehiko; Weiner, Peter (1970), "Sobre la minimización de estados de autómatas finitos no deterministas", IEEE Transactions on Computers , 100 (7): 617–627, doi : 10.1109 / TC.1970.222994 , S2CID 31188224.
- Knuutila, Timo (2001), "Re-describir un algoritmo por Hopcroft", Ciencias de la computación teóricas , 250 (1–2): 333–363, doi : 10.1016 / S0304-3975 (99) 00150-4 , MR 1795249.
- Leiss, Ernst (1981), "Representación sucinta de lenguajes regulares por autómatas booleanos", Informática teórica , 13 (3): 323–330, doi : 10.1016 / S0304-3975 (81) 80005-9 , MR 0603263.
- Leiss, Ernst (1985), "Representación sucinta de lenguajes regulares por autómatas booleanos II", Informática teórica , 38 : 133-136, doi : 10.1016 / 0304-3975 (85) 90215-4
- Moore, Edward F. (1956), "Experimentos de Gedanken en máquinas secuenciales", Estudios de autómatas , Anales de estudios de matemáticas, no. 34, Princeton, Nueva Jersey: Princeton University Press, págs. 129-153, MR 0078059.
- Sakarovitch, Jacques (2009), Elementos de la teoría de los autómatas , traducido del francés por Reuben Thomas, Cambridge University Press , ISBN 978-0-521-84425-3, Zbl 1188.68177
enlaces externos
- Minimización de DFA mediante el teorema de Myhill-Nerode