10

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.

Paŭlo Ebermann
  • 73,284
  • 20
  • 146
  • 210
franvergara66
  • 10,524
  • 20
  • 59
  • 101
  • 4
    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? – S.Lott Aug 01 '11 at 22:05
  • 3
    this should be at http://cstheory.stackexchange.com/ – Gabriel Ščerbák Aug 01 '11 at 22:07
  • What do you mean "equivalent"? You say they generate the same language. Do you mean the graphs are isomorphic? – Patrick87 Aug 01 '11 at 22:09
  • ...and it is important to say what kind of automa are we comparing here – Gabriel Ščerbák Aug 01 '11 at 22:10
  • @Patrick87 As he says, two automata are equivalent, if they recognize the same language. – Gabriel Ščerbák Aug 01 '11 at 22:12
  • @Gabriel, he said "deterministic" or "nondeterministic". That narrows it down to two, and the two are mathematically equivalent. Tada. – riwalk Aug 01 '11 at 22:13
  • @Stargazer712 there aren't just finite state automata (that he might be reffereing to) - e.g. look up pushdown automata. – Gabriel Ščerbák Aug 01 '11 at 22:15
  • @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 – franvergara66 Aug 01 '11 at 22:18
  • 1
    DFA = AFD, NFA = AFN, NFA-lambda = AFN-lambda – franvergara66 Aug 01 '11 at 22:20
  • @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. – Patrick87 Aug 01 '11 at 22:21
  • 3
    @patrick The automatons don't generate languages, automatons recognize languages – franvergara66 Aug 01 '11 at 22:23
  • @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. – riwalk Aug 01 '11 at 22:23
  • 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 – franvergara66 Aug 01 '11 at 22:26
  • @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... – Gabriel Ščerbák Aug 01 '11 at 22:28
  • 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. – Patrick87 Aug 01 '11 at 22:28

3 Answers3

20

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

Guy
  • 14,178
  • 27
  • 67
  • 88
12

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.

riwalk
  • 14,033
  • 6
  • 51
  • 68
  • 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. – Patrick87 Aug 01 '11 at 22:32
  • @Patrick87 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? – Gabriel Ščerbák Aug 01 '11 at 22:37
  • 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). – Patrick87 Aug 01 '11 at 22:41
  • 1
    @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. – Paŭlo Ebermann Aug 01 '11 at 22:48
  • @Patrick87 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:) – Gabriel Ščerbák Aug 01 '11 at 22:49
  • 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. – Patrick87 Aug 01 '11 at 22:56
  • 1
    @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. – supercat Dec 13 '12 at 17:21
  • 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 https://www.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. – Suzanne Soy Sep 13 '16 at 10:32
  • 1
    @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. – riwalk Sep 13 '16 at 16:19
  • 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. – 0lt May 12 '18 at 12:51
1

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:

Community
  • 1
  • 1
foxtrot9
  • 324
  • 5
  • 14