Equivalence between two automata

问题:

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.

回答1:

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.

回答2:

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).

回答3:

I am just rephrasing answer by @Guy.

To compare languages accepted by both we have to figure out if L(A) is equal to L(B) or not.

Thus, you have to find out if L(A)-L(B) and L(B)-L(A) is null set or not. (Reason1)

Part1:

To find this out, we construct NFA X from NFA A and NFA B, .

If X is empty set then L(A) = L(B) else L(A) != L(B). (Reason2)

Part2:

Now, we have to find out an efficient way of proving or disproving X is empty set. When will be X empty as DFA or NFA? Answer: X will be empty when there is no path leading from starting state to any of the final state of X. We can use BFS or DFS for this.

---

Reason1: If both are null set then L(A) = L(B).

Reason2: We can prove that set of regular languages is closed under intersection and union. Thus we will able to create NFA X efficiently.

and for sets: