# 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. – skankhunt42 Jan 29 '17 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? – Yuval Filmus Jan 29 '17 at 19:01
• Note: \langle and \rangle are what you want. – Raphael Jan 29 '17 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? – Marik S. Jan 30 '17 at 11:34
• Given a DFA, the language it accepts is non-empty iff some accepting state is reachable from the initial state. – Yuval Filmus Jan 30 '17 at 13:16

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