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.

Cottontail

You should flag your homework with [homework]. That makes it easier for us to provide appropriate help. You should provide your best answer so we can comment on it. Please don't ask us to do your homework for you. What do you learn then? – Cockerham

this should be at cstheory.stackexchange.com – Ellon

What do you mean "equivalent"? You say they generate the same language. Do you mean the graphs are isomorphic? – Lusk

...and it is important to say what kind of automa are we comparing here – Ellon

@Lusk As he says, two automata are equivalent, if they recognize the same language. – Ellon

@Gabriel, he said "deterministic" or "nondeterministic". That narrows it down to two, and the two are mathematically equivalent. Tada. – Masaccio

@Stargazer712 there aren't just finite state automata (that he might be reffereing to) - e.g. look up pushdown automata. – Ellon

@stargazer712 I mean that both are, or deterministic automatons or nondeterministic automatons, it is well known that there is equivalence between the AFD, AFN and AFN-lambda – Cottontail

DFA = AFD, NFA = AFN, NFA-lambda = AFN-lambda – Cottontail

@Gabriel: you are misreading the question. He asks how to determine whether automata are equivalent, if it is given that they accept the same language. Maybe this isn't what he meant, but that's what he wrote. – Lusk

@patrick The automatons don't generate languages, automatons recognize languages – Cottontail

@Gabriel, I've never heard of a Nondeterministic Finite Automota being mixed up with a Nondeterministic Pushdown Automota. I'm very familiar with both, and it seems very clear to me that he is referring to NFA's and DFA's, not NPDA's. – Masaccio

The PDA recognize context-free languages, DFS and the NFA do not recognize it, so can not establish equivalence between PDA and NFA or DFA – Cottontail

@Stargazer712 technically, we both assumed correctly, yet he could have ment anything, however the equivalence between PDA and DPDA isn't simple... and there are also LBAs... – Ellon

Melkhia66: I understand this. What don't you understand about equivalence between finite automata? Your question, as written, doesn't make a lot of sense. – Lusk

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

Masaccio

An alternative would be to generate any DFAs for the NFAs (e.g. by the subset construction), compute the complement of one of the two DFAs (e.g. by making accepting states rejecting and vice versa), building the Cartesian product machine and testing the intersection to see whether it accepts the empty language (e.g., by testing strings of length up to n). I wouldn't call this efficient, but you'd still need to test graph isomorphism on the output of Stargazer712's answer. – Lusk

@Lusk determining the sufficient n might not be easy, or is there some algorithm for computing it? And what do you mean by need to test the graph isomorphism? – Ellon

After you generate two minimal DFAs for the original FAs, how do you algorithmically determine they are the same? Sounds like a graph isomorphism problem to me. By the pumping lemma, you only need to choose n = the number of states in your final (minimal, if desired) FA. Alternatively, you can minimize the CP machine and check a very easy instance of graph isomorphism (only the start state, no accepting states). – Lusk

@Patrick: I think determining the equivalence of two minimal DFA's should be easy, simply do a BFS through both in the same order. As the corresponding edges should be labeled by the same characters, simply sort the outgoing edges from each state by those. – Barranca

@Lusk ah ok, but that largely depends on the choosen representation, but you are right. So you suggest to guess the right n, because it exists? How computer sciencey:) – Ellon

N is the number of states in a DFA. To see if a DFA accepts any strings, you can just test strings of length up to n. If the DFA doesn't accept any of these, then the DFA doesn't accept anything, by the pumping lemma. As to needing graph isomorphism... Yeah, come to think of it, you can probably do it easier than general graph isomorphism, since DFAs have uniquely labeled outgoing arcs. Good observation. – Lusk

@Patrick87: DFA equivalence is much easier. Define an equivalence relation Q[k] of states behave identically for all inputs of no more than k characters. Two states are in Q[k+1] if, for any given input character, they would both go to states which are equivalent in Q[k]. If the machine has n states, two states which cannot be distinguished within n characters will be indistinguishable for any input, and are thus equivalent. Even a really horrible naive implementation of that algorithm would be at worst O(n^3), so it's clearly not NP-hard. – Bouquet

Please avoid answers which rely on a link to an external source. Instead, include in your answer the relevant information, and provide the link as a reference. The cs.oberlin.edu/~jdonalds/331.huh/lecture05.html link you gave is now dead, and is not present on archive.org, as a result the answer is much less useful now than it was when initially posted. – Bundy

@GeorgesDupéron, fair enough. I removed that paragraph from the answer, as it was not necessary, nor does it even answer the original question. Anyone studying this topic should be very familiar with the techniques of reducing an NFA to a DFA anyway. – Masaccio

If two deterministic finite automata are equivalent, does that imply them having the exact same number of states and the same extended transition function? Assuming the unreachable states have been eliminated. – Boschbok

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

Yaws

Answer 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:

Gurl