¿Existe una prueba general para la equivalencia de dos máquinas de estado finito (determinísticas) que siempre toma tiempo finito? Es decir, dado dos FSM, ¿puede probar que, dadas las mismas entradas, siempre producirán las mismas salidas sin realmente tener que ejecutar los FSM (que podrían ser no terminantes?). Si tal prueba existe, ¿cuál es la complejidad del tiempo?Prueba general de equivalencia de dos FSM en tiempo finito?
Hay una prueba, aunque no lo sé. Busque el libro de texto de Sipser sobre el tema, de eso es de lo que yo sé.
Scrounging my memory: básicamente, hay un DFA mínimo único para un DFA específico, y hay un algoritmo de minimización que siempre termina. Minimice tanto A como B, y vea si tienen el mismo DFA mínimo. No sé la complejidad de la minimización, aunque no está tan mal (creo que es un polinomio). El isomorfismo gráfico es bastante difícil de calcular, pero debido a que hay un nodo inicial especial, es posible que sea algo más fácil. Puede que ni siquiera necesites isomorfismo gráfico, para ser honesto.
Pero no, nunca necesita ejecutar los DFA, simplemente analice su estructura.
Supongamos que tiene dos FSM con estados O (n). A continuación, puede crear un FSM de tamaño O (n) que reconozca solo la diferencia simétrica de sus idiomas de aceptación. (Cree un FSM que tenga estados que correspondan a un par de estados, uno de cada FSM. Luego, en cada paso, actualice cada parte del par de forma simultánea. Un estado en el nuevo FSM es un estado de aceptación si es exactamente uno de los dos pares un estado de aceptación.) Ahora minimice este FSM y vea si es lo mismo que el FSM de un estado trivial que rechaza todo. Minimizar un FSM con m estados toma O (m registro m), por lo general se puede hacer todo en tiempo O (n registro n).
@Agor dice correctamente que Sipser es una buena referencia para este tipo de cosas. El punto clave de mi respuesta es que puedes hacer esto en tiempo polinomial, incluso con un pequeño exponente.
El isomorfismo de gráfico no se conoce como NP-completo y, de hecho, se cree que no lo es. –
Tienes toda la razón, mi error. He editado la publicación para arreglar eso. – agorenst