Algoritmo de Brzozowski para la minimización de DFA

El algoritmo de minimización de DFA de Brzozowski crea un DFA mínimo para DFA $G$ de la siguiente manera:

1. invirtiendo todos los bordes en $G$ , haciendo que el estado inicial sea un estado de aceptación, y los estados de aceptación iniciales, para obtener un NFA $N'$ para el lenguaje inverso,
2. usando la construcción de powerset para obtener $G'$ para el lenguaje inverso,
3. invertir los bordes (y el intercambio de aceptación inicial) en $G'$ para obtener un NFA $N$ para el idioma original, y
4. $G_{\min}$

Por supuesto, dado que algunos DFA tienen un DFA inverso grande exponencial, este algoritmo se ejecuta en tiempo exponencial en el peor de los casos en términos del tamaño de la entrada, por lo que permite realizar un seguimiento del tamaño del DFA inverso.

Si es el tamaño de la entrada DFA, es el tamaño de la mínima DFA, y el tamaño de la mínima DFA inversa, a continuación, lo que es el tiempo de ejecución del algoritmo de Brzozowski en términos de , , y ?n m N n m$N$$n$$m$$N$$n$$m$

En particular, ¿bajo qué relación entre y el algoritmo de Brzozowski supera a los algoritmos de Hopcroft o Moore?$n$$m$

He oído que en ejemplos típicos en la práctica / aplicación , el algoritmo de Brzozowski supera a los demás. Informalmente, ¿cómo son estos ejemplos típicos?

Aquí hay una respuesta parcial con respecto a su tercera pregunta. De hecho, quizás el algoritmo de Brzozowski realmente no supera a todos los otros algoritmos tan claramente en la minimización de DFA.

En [1], los autores investigan el rendimiento práctico de los algoritmos de minimización de DFA / NFA. Los algoritmos son Hopcroft, Brzozowski y dos variantes de Watson. Llegan a la conclusión de que no hay un ganador claro, pero el algoritmo de Hopcroft funciona mejor para DFA con alfabetos pequeños. Para los NFA, Brzozowski es claramente el más rápido.

El documento en sí es bastante corto y está claramente escrito. También hay discusiones adicionales y referencias que pueden ser útiles.

[1] Almeida M., Moreira N. y Reis R. Sobre el desempeño de los algoritmos de minimización de autómatas, Cuarta Conferencia sobre Computabilidad en Europa, junio de 2008.

La mayor parte de lo siguiente es de Parsing Theory de Sippu y Soisalon-Soininen.

Sea el conjunto de estados del DFA. Deje T ser el alfabeto de entrada. Dejar | M | = O ( | T | ⋅ | Q | ) sea ​​el tamaño de la máquina. El ejercicio 3.40 proporciona un algoritmo O ( | T | ⋅ | Q | 2 ) para minimizar el estado. Como describe Wikipedia , el algoritmo de Hopcroft tiene un tiempo de ejecución de O ( | T | ⋅ | Q | ⋅ $Q$$T$$|M|=O(|T| \cdot |Q|)$$O(|T|\cdot|Q|^2)$ y el algoritmo de Moore tiene un tiempo de ejecución de O ( | T | 2 ⋅ | Q | ) .$O(|T| \cdot |Q| \cdot \log|T|)$$O(|T|^2 \cdot |Q|)$

El teorema 3.30 establece que la construcción del subconjunto se puede hacer en produciendo un autómata de tamaño O ( 2 | T | + log | Q | ) (en realidad, si el el autómata resultante tiene | T ′ | estados, el tiempo de ejecución es ( | T ′ | + | T | ⋅ |$O(2^{|T|+\log|T|+\log|Q|})$$O(2^{|T|+\log|Q|})$$|T'|$) Por lo tanto, las dos reversiones y la segunda determinación son intrascendentes en el tiempo de ejecución, por lo que el tiempo de ejecución asintótico del algoritmo de Brzozowski es el mismo que el de la construcción del subconjunto.$(|T'| + |T|\cdot|M|) \cdot |Q|$

Esto significa que, en el peor de los casos, el algoritmo de Brzozowski es exponencialmente más lento que los otros tres algoritmos. Tenga en cuenta que el peor de los casos realmente ocurre: el ejemplo clásico de NFA para el lenguaje tiene estados k + 1 y su DFA mínimo correspondiente tiene estados O ( 2 k ) , mientras que el reverso de NFA es determinista, por lo que ejecutar el algoritmo de Brzozowski en este NFA invertido desencadena el peor de los casos.$(a|b)^*a^k$$k+1$$O(2^k)$

Sin embargo, si la construcción del subconjunto produce un autómata de tamaño , entonces su tiempo de ejecución también es O ( | T | 2 ⋅ | Q | 2 ) , que suele ser el caso en las entradas de la vida real. Además, si se tiene el cuidado adecuado al calcular el cierre de un estado, esto puede hacerse mucho más rápido en la mayoría de los casos (es decir, casos en los que el cierre es pequeño), ahorrando un factor | T $|T'|=O(|T|)$$O(|T|^2 \cdot |Q|^2)$$|T|$en la práctica (esencialmente por la misma razón por la que los cierres transitivos se pueden calcular con bastante rapidez en ejemplos del mundo real). Además, si la entrada y los autómatas intermedios son escasos, lo que significa que los estados tienen pocas transiciones, entonces un factor se guarda, lo que da un tiempo de ejecución O ( | T | ⋅ | Q | ) en las entradas 'buenas'.$|Q|$$O(|T| \cdot |Q|)$

Desafortunadamente, no estoy lo suficientemente familiarizado con los algoritmos de Hopcroft o Moore para dar un análisis de sus tiempos de ejecución en casos típicos. Wikipedia habla sobre un tiempo de ejecución en algunos casos, lo que haría que los tres algoritmos fueran comparables.$O(|T| \log \log |T|)$

De Felice y Nicaud muestran que los algoritmos de Brzozowski son asintóticamente hiperpolinomiales. David ha demostrado que, para varias distribuciones en estados finales, el algoritmo de Hopcroft es más lento que el algoritmo de Moore.

Referencias

S. De Felice y C. Nicaud, "El algoritmo de Brzozowski es genéricamente superpolinomial para autómatas deterministas". En Actas de la 17ª Conferencia Internacional sobre Desarrollos en Teoría del Lenguaje (DLT 2013) , Lecture Notes in Computer Science, pp. 170-190, 2013. ( PDF )

J. David, "Complejidad promedio de los algoritmos de Moore y Hopcroft". Informática teórica , 417: 50–65, 2012. ( Science Direct )