la preuve générale de l'équivalence des deux FSMs en temps fini?

Question

Est-ce une preuve générale existe pour l'équivalence des deux (déterministe) machines à états finis qui prend toujours le temps fini? Ainsi, compte tenu deux FSMs, pouvez-vous prouver que étant donné les mêmes intrants qu'ils produiront toujours les mêmes résultats sans réellement besoin pour exécuter les FSMs (qui pourrait être non-terminaison?). Si une telle preuve existe, quelle est la complexité du temps?

Answer 1

Il y a une preuve, bien que je ne le sais pas. Recherchez le manuel de Sipser sur le sujet, c'est là que je connais partir.

Scrounging ma mémoire: au fond, il y a un minimum DFA unique pour un DFA donné, et il y a un algorithme de minimisation qui se termine toujours. Réduire au minimum A et B, et voir si elles ont le même DFA minimal. Je ne sais pas la complexité de la minimisation, bien que son pas trop mal (je pense que son polynôme). Graph est isomorphie assez difficile à calculer, mais parce qu'il ya un nœud de départ spécial, il peut être un peu plus facile, espérons. Vous pouvez même pas besoin graphique isomorphisme, pour être honnête.

Mais non, vous ne devez jamais exécuter réellement la DFA, analyser simplement leur structure.

Answer 2

Supposons que vous ayez deux FSMs avec O ( n ) états. Ensuite, vous pouvez faire une EFM de taille O ( n ² ) qui ne reconnaît que la différence symétrique de leurs langues accepter. (Faire un FSM qui a des états qui correspondent à une paire d'états, un de chaque EFM. Ensuite, à chaque étape, mettez à jour chaque partie de la paire simultanément. Un état dans la nouvelle FSM est un accept état ssi exactement un des deux a été accept état.) minimiser maintenant, ce FSM et voir si elle est la même chose que le trivial États fédérés de Micronésie un Etat qui rejette tout. Réduire au minimum un EFM avec m états prend du temps O ( m log m ), vous pouvez donc globalement tout en temps O ( n ² log n ).

@Agor indique à juste titre que Sipser est une bonne référence pour ce genre de choses. Le point clé de ma réponse est que vous pouvez le faire en temps polynomial, même avec un petit exposant.