12
$\begingroup$

Inspired by this question, I am curious about the following:

What is the worst-case complexity of checking whether a given DFA accepts the same language as a given regular expression?

Is this known? The hope would be that this problem is in P -- that there is an algorithm polynomial in the size of both.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
16
$\begingroup$

According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does not generate all strings. So your problem is also PSPACE-complete.

Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct an NFA $B$ for $r$, and use the power set construction to virtually construct a DFA $C$ equivalent to $B$; we will not keep $C$ in memory, but we have oracle access to $C$ using only polynomial space. Now virtually construct a DFA $D$ for the symmetric difference of $A$ and $C$ using the product construction. This DFA accepts no strings (and so $L(A) = L(r)$) if there is no path from the starting state to an accepting state. Since reachability is in NL and $D$ has size $2^{\mathrm{poly}(n)}$, we can check whether $L(D) = \emptyset$ in $\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$, the latter equality due to Savitch's theorem.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Are you sure it's in PSPACE (if not it would just be PSPACE-HARD)? Or maybe it's enough to check all the strings of some polynomial length to see if the regexp and the DFA agree on all of them? Is that obvious? :-) $\endgroup$
    – Neal Young
    Jan 4, 2013 at 3:33
  • 4
    $\begingroup$ Remember reachability is in NL, so even though the DFA corresponding to the regular expression is exponential, since oracle access to it is cheap, we can figure out whether the symmetric difference is empty or not in NPSPACE=PSPACE. $\endgroup$
    – Yuval Filmus
    Jan 4, 2013 at 5:01
  • $\begingroup$ I don't see the hardness result. That is, how do you reduce the problem above to universality of regular expressions? $\endgroup$
    – Markus
    Jan 4, 2013 at 12:20
  • 2
    $\begingroup$ Choose the DFA that accepts everything. To show hardness, you reduce REGULAR EXPRESSION NON-UNIVERSALITY to the problem in question. $\endgroup$
    – Yuval Filmus
    Jan 4, 2013 at 16:45
  • 1
    $\begingroup$ @YuvalFilmus Thanks for the reference! You should probably add your first comment to your answer for completeness, in both meanings of the word :) $\endgroup$
    – Lev Reyzin ♦
    Jan 4, 2013 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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