[Solved]: How do I verify that a DFA is equivalent to a NFA?

Problem Detail: 

I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is equivalent to a NFA?

Asked By : IAmOnStackExchange

Answered By : Shaull

This is a problematic question. There is a way to check equivalence of automata, which I'll now explain, but I'm afraid it won't help you, as you will see at the end.

Recall that two sets $A$ and $B$ are equal iff $A\subseteq B$ and $B\subseteq A$ (this is the definition of set equality). Thus, it is enough for you to verify that $L(D)\subseteq L(N)$ and $L(N)\subseteq L(D)$, where $D$ and $N$ are your DFA and NFA, respectively.

But how do you check containment of languages, you might ask. Well, now observe that $A\subseteq B$ iff $A\cap \overline{B}=\emptyset$ (where $\overline{B}$ is the complement of $B$).

Let's consider first checking whether $L(N)\subseteq L(D)$. To do this, you need to complement $D$ (very easy - swap the accepting an rejecting states), then construct the intersection automaton (e.g. with the product construction) with $N$, and check for emptiness, by finding a path to an accepting state.

The converse direction, however, will show why this doesn't help you. In order to check whether $L(D)\subseteq L(N)$, you need to complement $N$. But in order to complement an NFA, you first need to convert it to a DFA, rendering the whole idea pointless.

Essentially, the problem with your question is much deeper: you want to verify that you (an undefined computational model) executed a well-defined algorithm properly. So this is not really a computer-science problem.

I will say this: following the constructions I suggested, it is not hard to conclude that $L(D)\neq L(N)$ iff there is a word of length at most $2^{2n}$ ($n$ being the number of states of $N$) that is accepted by one and not by the other. So you can try all words up to this length.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50505