3
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.