Minimizando los Autómatas aceptando palabras

¿Cuál es el enfoque estándar para minimizar Büchi-Automata (o también Müller-Automata)? Transferir la técnica habitual de palabras finitas, es decir, establecer dos estados para que sean iguales si las palabras "agotándose" de los estados aceptados son las mismas, no funcionará. Por ejemplo, considere que Büchi-Automoton acepta todas las palabras con un número infinito de a que consta de dos estados, un estado inicial y un estado final, y el estado final se ingresa cada vez que se lee un a, y el estado inicial se ingresa cada vez que un Se lee un símbolo diferente. Ambos estados se consideran iguales por la definición anterior, pero al colapsarlos se obtiene un autómata que consta de un solo estado y, por lo tanto, acepta todas las palabras.

En general, los lenguajes regulares pueden no tener un DBW mínimo único. Por ejemplo, el lenguaje "infinitamente muchos a's e infinitamente muchos b's" tiene dos DBW de 3 estados (en la imagen reemplace ¬ a por b ): $\omega$$\neg a$$b$

Como puede ver, no son topológicamente equivalentes.

Por lo tanto, el problema de minimización es más difícil que el caso finito, y de hecho, es NP completo .

Esta pregunta generó mucha literatura en los años 80, en parte debido a un mal enfoque del problema. Esta es una historia bastante larga que trataré de resumir en esta respuesta.

1. El caso de las palabras finitas.

Se pueden encontrar dos definiciones de un DFA mínimo en la literatura. El primero es definir el DFA mínimo de un idioma regular como el DFA completo con el número mínimo de estados que aceptan el idioma. El segundo es más largo de definir, pero matemáticamente es más atractivo que el primero y le da propiedades más fuertes.

Recordemos que un DFA es accesible si para todo q ∈ Q , hay una palabra u ∈ A ∗ tal que i ⋅ u = q . Es completa si q ⋅ una está definida para todo q ∈ Q y un ∈ A .$(Q, A, \cdot, i, F)$$q \in Q$$u \in A^*$$i \cdot u = q$$q \cdot a$$q \in Q$$a \in A$

Sea y A 2 = ( Q 2 , A , ⋅ , i 2 , F 2 ) sean dos DFA completos y accesibles. Un morfismo de A 1 a A 2 es una función φ : Q 1 → Q 2 tal que${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$$\mathcal{A}_1$$\mathcal{A}_2$$\varphi:Q_1 \to Q_2$

1. ,$\varphi(i_1) = i_2$
2. ,$\varphi^{-1}(F_2) = F_1$
3. para todos y a ∈ A , φ ( q ) ⋅ a = φ ( q ⋅ a ) .$q \in Q_1$$a \in A$$\varphi(q)\cdot a=\varphi(q\cdot a)$

Se puede demostrar que estas condiciones implican que es necesariamente sobreyectivo (y por lo tanto | Q 2 | ⩽ | Q 1 | ). Además, hay a lo sumo un morfismo de A 1 a A 2 y si este morfismo existe, entonces A 1 y A 2 reconocen el mismo lenguaje. Ahora, uno puede mostrar que para cada idioma L , hay un DFA A L accesible completo completo que acepta L y tal que, para cada DFA A accesible completo que acepta $\varphi$$|Q_2| \leqslant |Q_1|$${\cal A}_1$${\cal A}_2$${\cal A}_1$${\cal A}_2$$L$${\cal A}_L$$L$$\cal A$$L$, Hay un morfismo de a A L . Este autómata se llama el DFA mínimo de L . Tenga en cuenta nuevamente que, dado que el número de estados en A L es menor que el número de estados en A , A L también es mínimo en el primer sentido.$\cal A$${\cal A}_L$$L$${\cal A}_L$$\cal A$${\cal A}_L$

Vale la pena mencionar que también existe una definición algebraica adecuada para DFA incompletos . Ver [Eilenberg, Automata, Languages ​​and Machines , vol. A, Academic Press, 1974] para más detalles.

2. Volver a las palabras infinitas.

Extender la primera definición no funciona, como lo muestra Shaull en su respuesta. Y desafortunadamente también se puede demostrar que la propiedad universal de la segunda definición no se extiende a palabras infinitas, excepto en algunos casos particulares.

¿Es el final de la historia? Espera un segundo, hay otro objeto mínimo que acepta lenguajes regulares ...

3. El enfoque sintáctico

Volvamos primero a las palabras finitas. Recordemos que un lenguaje de A * es reconocido por un monoide M si hay una sobreyectiva monoid morfismo f : A * → M y un subconjunto P de M tal que f - 1 ( P ) = L . Nuevamente, existe un monoide M ( L ) , llamado monoide sintáctico de L , que reconoce L y es un cociente de todos los monoides que reconocen $L$$A^*$ $M$$f:A^* \to M$$P$$M$$f^{-1}(P) = L$$M(L)$$L$$L$$L$. Este monoide sintáctico se puede definir directamente como el cociente de por la congruencia sintáctica ∼ L de L , definida de la siguiente manera: u ∼ L v  si y solo si, para todo  x , y ∈ A ∗ ,  x u y ∈ $A^*$ $\sim_L$$L$ La buena noticia es que esta vez, este enfoque se ha extendido a palabras infinitas, pero llevó mucho tiempo descubrir las nociones apropiadas. Primero, A. Arnold encontró la noción adecuada de una congruencia sintáctica (Una congruencia sintáctica para losidiomasωracionales,Theoret. Comput. Sci.39, 2-3 (1985), 333-335). Extender los monoides sintácticos a la configuración de palabras infinitas requería un tipo de álgebras más sofisticado, llamado hoyendíaálgebras de Wilkeen honor a T. Wilke, quien fue el primero en definirlas (T. Wilke, una teoría algebraica para lenguajes regulares de finito e infinito). palabras,Int. J. Alg. Comput.3

4. Conclusión

Por lo tanto, existe una noción matemáticamente sólida de un objeto mínimo que acepta un lenguaje regular dado , pero no se basa en autómatas. Esto es en realidad un hecho bastante genérico: los autómatas son una herramienta algorítmica muy poderosa, pero no siempre son suficientes para tratar preguntas matemáticas en idiomas.$\omega$