El algoritmo de Brzozowski para convertir un DFA en un DFA de estado mínimo equivalente es notablemente simple: si denota el NFA formado al invertir todos los bordes en un DFA , haciendo que el estado inicial anterior sea un estado de aceptación, y haciendo que el anterior acepte estados comienzan estados, y si denota el resultado de aplicar la construcción de subconjuntos a la NFA , entonces es de un mínimo de estado DFA con el mismo idioma que .
Podemos pensar en un DFA como un dispositivo computacional que acepta una cadena de entrada y luego emite 0 si termina en un estado de rechazo y 1 si termina en un estado de aceptación. Una generalización natural de los DFA asociaba cada estado en el DFA con algún número natural entre 0 y , inclusive.
Hasta donde sé, es posible minimizar estas clases modificadas de DFA mediante el uso de un algoritmo de minimización basado en la distinción, como el canónico de Hopcroft. Sin embargo, no puedo ver cómo sería posible adaptar el algoritmo de minimización de Brzozowski a esta nueva clase de autómatas porque el paso clave (invertir el autómata) ya no tiene una interpretación clara en esta configuración generalizada.
¿Existe una generalización conocida del algoritmo de Brzozowski para minimizar este tipo de autómatas? Si no, ¿hay alguna razón teórica por la que esperaríamos que no existiera un algoritmo tan modificado?
fuente
Respuestas:
La respuesta a tu pregunta es sí.
Véanse los documentos de Bonchi, Bonsangue, Rutten y Silva. El algoritmo de Brzozowski (co) algebraicamente (versión de conferencia más corta) y la dualidad de álgebra-coalgebra en el algoritmo de minimización de Brzozowski (versión de revista más larga con más generalizaciones).
Ofrecen una presentación (ligeramente) categórica del algoritmo de Brzowzowski y lo utilizan para derivar versiones del mismo para clases más generales de autómatas, incluido el autómata de Moore (que da una respuesta afirmativa a su pregunta).
fuente
Solo para agregar a la respuesta de Neel, en mi libro Secuencias automáticas con Jean-Paul Allouche discutimos los DFAO (autómatas finitos deterministas con salidas), que son exactamente lo que preguntaste (asociar una salida con cada estado). Y el teorema 4.3.3 describe cómo invertir una máquina de este tipo.
fuente