Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 16 down vote accepted

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.

share|improve this answer
    
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? :-) –  Neal Young Jan 4 '13 at 3:33
4  
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. –  Yuval Filmus Jan 4 '13 at 5:01
    
I don't see the hardness result. That is, how do you reduce the problem above to universality of regular expressions? –  Markus Jan 4 '13 at 12:20
2  
Choose the DFA that accepts everything. To show hardness, you reduce REGULAR EXPRESSION NON-UNIVERSALITY to the problem in question. –  Yuval Filmus Jan 4 '13 at 16:45
1  
@YuvalFilmus Thanks for the reference! You should probably add your first comment to your answer for completeness, in both meanings of the word :) –  Lev Reyzin Jan 4 '13 at 19:04
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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