la prova generale di equivalenza dei due FSM in tempo finito?

Question

Esiste una dimostrazione generale esiste per l'equivalenza delle due (deterministici) macchine a stati finiti che prende sempre tempo finito? Cioè, dato due FSM, si può dimostrare che, dati gli stessi ingressi saranno sempre produrre le stesse uscite senza effettivamente dover eseguire i FSM (che poteva essere non-terminazione?). Se una tale prova esiste, qual è la complessità temporale?

Answer 1

C'è una prova, anche se non lo conosco. Cercare libro di testo di Sipser in materia, è lì che io sappia da.

Scrounging mia memoria: in fondo, c'è una minima DFA unico per un dato DFA, e non v'è un algoritmo di minimizzazione che termina sempre. Ridurre al minimo sia A che B, e vedere se hanno lo stesso minimo DFA. Non conosco la complessità della minimizzazione, anche se la sua non troppo male (credo che il suo polinomiale). Grafico isomorfismo è piuttosto difficile da calcolare, ma perché c'è un nodo di partenza speciale, può essere un po 'più facile si spera. Si può anche non richiedere grafico isomorfismo, ad essere onesti.

Ma no, non è mai bisogno di eseguire in realtà il DFA, basta analizzare la loro struttura.

Answer 2

Supponiamo di avere due FSM con O ( n ) stati. Poi si può fare una FSM di dimensione O ( n ² ) che riconosce solo la differenza simmetrica delle loro lingue accettare. (Effettuare una FSM che ha stati che corrispondono ad una coppia di stati, uno per ogni FSM. Poi ad ogni passo, modificare ogni parte della coppia simultaneamente. Uno stato nel nuovo FSM è una accept stato sse esattamente uno della coppia fu un accettare di stato.) Ora, ridurre al minimo questo FSM e vedere se è la stessa come il banale FSM un solo stato che rifiuta tutto. Ridurre al minimo l'FSM con m Stati richiede tempo O ( m log m ), quindi nel complesso si può fare tutto in tempo O ( n ² log n ).

@Agor afferma correttamente che Sipser è un buon riferimento per questo genere di cose. Il punto chiave della mia risposta è che si può fare questo in tempo polinomiale, anche con un piccolo esponente.