Check if 2 minimum DFA are equivalent

Question

I have 2 minimized DFA and i need to check if they are equivalent.

If they are equivalent, the problem is to find a efficient comparison of state regardless of different labels. In my case DFA are table, then i need to find the permutation that match the rows of first DFA with rows of second DFA.

I thought also about to have a Breadth-first search of DFA and create the minimum access string to a state and then compare the first list with the second list (this should be regardless of the particular input, for example: 001 and 110 could be interchangeable).

I'm interesting either to direct and inefficient algorithm and to more sophisticated algorithm.

Answer 1

I found these algorithms:

 - Symmetric difference
 - Table-filling algorithm
 - Faster Table-Filling algorithm O(n^2)
 - Hopcroft algorithm
 - Nearly Linear algorithm by Hopcroft and Karp

A complete reference is:

• Algorithms for testing equivalence of finite automata, with a grading tool for Jflap - Norton, 2009

I accepted this my answere because the one of @abbaasi is too incomplete. I will accept any other answer with a significant contribution.