El algoritmo de Brzozowski se puede extender a los autómatas de Moore, pero su complejidad temporal es exponencial en general. ¿Hay algún otro algoritmo para minimizar los autómatas de Moore? ¿Cuáles son los tiempos de ejecución de estos algoritmos si los hay?
10
Respuestas:
El algoritmo de minimización DFA original fue diseñado para máquinas Moore , guiado por su comportamiento aparentemente más observable. Pero el algoritmo presentado aquí es una reconstrucción de la minimización de DFA, ya que descubrí la evidencia histórica después del hecho.
Después de Wikipedia (con algunos cambios notacionales):
A partir de esta definición, una máquina Moore es un transductor determinista de estado finito.
No tengo referencia para la minimización de los autómatas de Moore. Sin embargo, no parece demasiado difícil imaginar un algoritmo, derivado del algoritmo utilizado para autómatas deterministas de estado finito.
La idea en la minimización de DFA se basa en la caracterización de Myhill-Nerode de los idiomas regulares .
Por lo tanto, la minimización del DFA en realidad consiste en fusionar estados (considerados como conjuntos de cadenas equivalentes), siempre que se demuestre que dos estados distintos contienen cadenas equivalentes.
El siguiente algoritmo imita el algoritmo de Moore para la minimización de DFA.
Cuando no quede ninguna clase que deba dividirse, las clases restantes de estados formarán los estados de la máquina mínima de Moore.
Por construcción, todos los estados en una clase tienen la misma salida que es la salida para la clase.
No tengo ninguna referencia para esta minimización de las máquinas Moore. Posiblemente está incluido en su artículo:
Este documento es la referencia principal que presenta las Máquinas Moore . También es la referencia para el algoritmo de minimización DFA de Moore . Por lo tanto, debería ser sorprendente si la adaptación del algoritmo a la minimización de las máquinas Moore no se sugiriera al menos en ese documento. Verifiqué el documento, y la versión del algoritmo de minimización que se presenta es en realidad para máquinas Moore, no para DFA. El documento está bien escrito, pero el estilo de la época hace que sea un poco más difícil de leer. Es interesante ver que muchas de las ideas de la teoría de Myhill-Nerode de las máquinas de estados finitos ya están esbozadas en este documento.
fuente
Una versión del algoritmo de Brzozowski usando derivadas de expresiones regulares se da en [2], Capítulo 12, Sección 4, donde se acredita a [4]. Ver [1] y [3] para el caso más general de transductores subsecuentes (la terminología está un poco desactualizada y el término transductor secuencial es probablemente más apropiado hoy en día).
[1] C. Choffrut, Minimizando transductores subsecuenciales: una encuesta, Theoret. Comp. Sci. 292 (2003), 131–143.
[2] S. Eilenberg, Autómatas, Idiomas y máquinas, vol. A, Academic Press, 1974.
[3] J.-E. Pin, un tutorial sobre funciones secuenciales . (Diapositivas)
[4] GN Raney, Funciones secuenciales, JACM 5 (1958), 177–180.
fuente
El algoritmo de Brzozowski es un mal punto de partida (si le preocupa el tiempo de ejecución asintótico del peor de los casos). Incluso Wikipedia te dice lo mismo:
El algoritmo tiene un tiempo de ejecución exponencial en el peor de los casos, incluso en DFA porque calcula un autómata para el reverso, que puede ser exponencialmente grande. Por lo tanto, su problema no proviene de la extensión a los transductores.
Intente adaptar otro algoritmo de minimización de DFA.
fuente