# An algorithm for comparing a DFA and a regular expression

Assuming I have an encoding of a DFA $<M>$ and a regular expression $<r>$, I'm interested in finding an algorithm for comparing whether or not $L(M)=L(r)$.

I have thought about converting $r$ into an NFA, and then converting the NFA to a DFA, but the problem is that this process may result in a totally different DFA.

Another idea I had was to convert the DFA to a regular expression. But with this idea, I have two problems: first is that I'm not sure how exactly is ut done, and second - even if I will succeed in doing so, I might again end up with a totally different regular expression (that has the same language, but written differently).

Obviously, a third approach would be to start looping all over $\Sigma^*$, but this is an infinet process...

Does someone have a different idea or a way to improve my approaches to this problem?

I would like my algorithm to be able to both return "true" if $L(M)=L(r)$ and false otherwise (my third approach can only return false, but will never return true).

• Do you know about DFA Minimization? Basically, every DFA has a unique equivalent minimal DFA that has the minimum number of states (upto renaming the states). You can overcome the problem of a 'totally different DFA' using this. Jan 29, 2017 at 18:32
• Another option is to compute a DFA for the symmetric difference. In both cases, the main problem is that the conversion from NFA to DFA is very costly. Can you think of a better approach? Jan 29, 2017 at 19:01
• Note: \langle and \rangle are what you want.
– Raphael
Jan 29, 2017 at 22:30
• I see, so DFA minimization is one option. @Yuval , how can I compute a DFA for the symmetric difference without first knowing the languages themselves? I can calculate the product automaton, but how will I be able to check if its empty? Jan 30, 2017 at 11:34
• Given a DFA, the language it accepts is non-empty iff some accepting state is reachable from the initial state. Jan 30, 2017 at 13:16

## 1 Answer

This technique I am going to describe works to compare two NFAs. Fortunately, you have mentioned that you know how to convert your regular expression into an NFA and it is trivial to convert your DFA into an NFA. (just treat the DFA as though it were an NFA)

Once you have your two NFAs, add two new symbols to your alphabet: $\$_1$and$\$_2$. We're going to construct a larger NFA by combining the two NFAs that we have. Add a node (call it $\omega$), and add edges from every accepting node in the first NFA to node $\omega$ labeled with $\$_1$. Now add edges from every accepting node in the second NFA to node$\omega$labeled with$\$_2$.

Now add another node (call it $\alpha$) and add epsilon-transition edges from $\alpha$ to the initial node in each NFA. (so $\alpha$ has only two edges leaving it). (alternatively, since some people don't like epsilon transitions, you can instead add to $\alpha$ all the outgoing edges of the initial nodes in each original NFA)

Now take this combined graph with the two extra nodes as an NFA: the initial node is $\alpha$, and the only accepting node in the combined graph is $\omega$.

Turn this NFA into a DFA. One side-effect of how we constructed edges into $\omega$ is that the DFA will have only a single accepting state. The two original languages will be identical if and only if in the DFA every edge going to this accepting node is labeled with both $\$_1$and$\$_2$.

Essentially, what we did was form the languages: \begin{align} L_1 &= \{ w \ \$_1 \ | \ w \in L(M)\} \\ L_2 &= \{ v \ \$_2 \ | \ v \in L(r)\} \end{align} and then our combined NFA was the NFA for the language $L_1 \cup L_2$. The statement about the edges of the DFA says that there exists some set $A$ such that the language of our DFA is $$\{a \ x \ | \ a \in A, x \in \{\_1, \_2\} \}$$ But this implies that if you stripped the $\$_i$symbols off the end of the strings in$L_1$and$L_2$you'd have the same language. Incidentally, you can use this DFA for$L_1 \cup L_2$to easily construct DFAs for$L(M) \cap L(r)$, for$L(M) \cup L(r)$, for$L(M) \setminus L(r)$, for$L(r) \setminus L(M)$, and for the symmetric difference of$L(M)$and$L(r)$. The exact details are left as an exercise for the reader, but it involves examining nodes with outgoing edges labeled with one of the$\$_i$ symbols, labeling some of those nodes as accepting nodes, and then erasing all edges labeled with the $\$_i$symbols. (These won't necessarily be minimal DFAs, even if you minimized the DFA before erasing the$\$_i$ edges. You'll need to apply standard DFA minimization algorithms if you want that.)