Equivalence between two automata

Question

Which is the best or easiest method for determining equivalence between two automata?

I.e., if given two finite automata A and B, how can I determine whether both recognize the same language?

They are both deterministic or both nondeterministic.

Answer 1

A different, simpler approach is to complement and intersect the automata. An automaton A is equivalent to B iff L(A) is contained in L(B) and vice versa which is iff the intersection between the complement of L(B) and L(A) is empty and vice versa.

Here is the algorithm for checking if L(A) is contained in L(B):

1. Complementation: First, determinize B using the subset construction. Then, make every accepting state rejecting and every rejecting state accepting. You get an automaton that recognizes the complement of L(B).
2. Intersection: Construct an automaton that recognizes the language that is the intersection of the complement of L(B) and L(A). I.e., construct an automaton for the intersection of the automaton from step 1 and A. To intersect two automata U and V you construct an automaton with the states U x V. The automaton moves from state (u,v) to (u',v') with letter a iff there are transitions u --a--> u' in U and v --a--> v' in V. The accepting states are states (u,v) where u is accepting in U and v is accepting in V.
3. After constructing the automaton in step 2, all that is needed is to check emptiness. I.e., is there a word that the automaton accepts. That's the easiest part -- find a path in the automaton from the initial state to an accepting state using the BFS algorithm.

If L(A) is contained in L(B) we need to run the same algorithm to check if L(B) is contained in L(A).

Answer 2

Two nondeterministic finite automota (NFA's) are equivalent if they accept the same language.

To determine whether they accept the same language, we look at the fact that every NFA has a minimal DFA, where no two states are identical. A minimal DFA is also unique. Thus, given two NFA's, if you find that their corresponding minimal DFA's are equivalent, then the two NFA's must also be equivalent.

For an in-depth study on this topic, I highly recommend that you read An Introduction to Formal Language and Automata.