prueba general de la equivalencia de dos FSM en tiempo finito?

Question

¿Existe una prueba general para la equivalencia de dos (deterministas) máquinas de estados finitos que siempre lleva tiempo finito? Es decir, dado dos FSM, se puede demostrar que, dadas las mismas entradas que siempre producirán los mismos resultados, pero sin necesidad de ejecutar las FSM (que podría ser no termina?). Si existe tal prueba, lo que es la complejidad de tiempo?

Answer 1

Hay una prueba, aunque yo no lo sé. Busque los libros de texto de Sipser sobre el tema, que es donde yo conozco de.

Scrounging mi memoria: básicamente, hay un mínimo de DFA único para un determinado DFA, y hay un algoritmo de minimización que siempre termina. Minimizar tanto A como B, y ver si tienen el mismo mínimo de DFA. No sé la complejidad de la reducción al mínimo, aunque no es demasiado malo (creo que su polinomio). isomorfismo de grafos es bastante difícil de calcular, pero porque hay un nodo de partida especial, puede espera que sea un poco más fácil. Puede que ni siquiera necesita isomorfismo de grafos, para ser honesto.

Pero no, usted no necesita nunca a ejecutar realmente la DFA, simplemente analizar su estructura.

Answer 2

Supongamos que tiene dos FSM con O ( n ) estados. A continuación, puede hacer una FSM de tamaño O ( n ² ) que reconoce sólo la diferencia simétrica de sus lenguas aceptar. (Hacer una MEF que tiene estados que corresponden a un par de estados, uno de cada FSM. Luego, en cada paso, actualizar cada parte de la pareja al mismo tiempo. Un estado en el nuevo FSM es un estado acepta si y sólo si exactamente uno de la pareja se un estado acepte.) Ahora minimizar este FSM y ver si es el mismo que el FSM trivial de un solo estado que rechaza todo. Minimizar un FSM con m Unidos toma tiempo O ( m log m ), por lo general se puede hacer todo en tiempo O ( n ² log n ).

@Agor afirma correctamente que Sipser es una buena referencia para este tipo de cosas. El punto clave de mi respuesta es que se puede hacer esto en tiempo polinómico, incluso con un pequeño exponente.