5
$\begingroup$

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ?

What I know so far is that there are decidable algorithms for transforming a regular expression into a NFA and then into a DFA, but these algorithms can take a long time and produce a DFA that takes up exponential space. I also know that $EQ_{DFA}$ is decidable.

So $EQ_{REX}$ is provably decidable because you can turn R and S into DFAs and then show that the DFAs are equivalent. But I'm not sure how to analyze the complexity of a machine like this, and something tells me that it is not in NP.

Is there a way to show that this particular machine is in PSPACE (or NPSPACE, because they are equivalent)? How would I analyze its complexity? Or am I taking the wrong approach entirely, and should instead try to show that this problem is reducible to some other PSPACE-complete problem?

$\endgroup$
5
  • 1
    $\begingroup$ Did you try anything yet? Where did you get stuck? $\endgroup$
    – Louis
    Apr 11, 2016 at 16:29
  • $\begingroup$ I've been trying to think of different ways to tackle it, but no luck so far. I've thought if you can prove it is in NP, then it is also in PSPACE, but I can't think of any possible poly-time verifier for it. I also can't come up with a PSPACE-complete problem to reduce it to, which is the route that seems more likely. $\endgroup$
    – Brandon G
    Apr 11, 2016 at 16:33
  • $\begingroup$ Welcome to CS.SE! Please edit the question to show us what you've tried and where you got stuck. Do you have any specific question about this problem? We want to help you understand concepts, not do your exercise for you, but you haven't given us much to work with, so it's not clear how to help you. Just copying the text of your exercise into the question doesn't work so well here, because it's hard to tell from that what you are stuck on or why you are having difficulty with the problem. Rather than leaving information in the comments, please edit the question. $\endgroup$
    – D.W.
    Apr 11, 2016 at 16:49
  • 1
    $\begingroup$ Have you been able to find any algorithm for testing whether regexps $R,S$ are equivalent? If so, what's the best algorithm you've come up with so far? How does it work? What is the space complexity of that algorithm? Do you know the definition of PSPACE? Do you know how to prove that an algorithm is in PSPACE? It sounds like you might need to review the definition of PSPACE. $\endgroup$
    – D.W.
    Apr 11, 2016 at 16:49
  • 2
    $\begingroup$ Maybe look at this question for inspiration. cs.stackexchange.com/questions/24390/… $\endgroup$
    – Louis
    Apr 12, 2016 at 6:57

2 Answers 2

4
$\begingroup$

Hint: One obvious algorithm for this problems goes as follows. Given two regular expressions $R,S$, convert them to NFAs $N_R,N_S$ and then to DFAs $D_R,D_S$. Using the product construction, construct a DFA for $D_R \Delta D_S$ (here $A \Delta B$ is the symmetric difference), and check whether the language it accepts is empty.

While this algorithm doesn't quite use polynomial space (why?), you can follow the same general plan to solve your problem. It might be helpful to use NPSPACE=PSPACE or perhaps coNPSPACE=PSPACE.


Here is a complete answer. Let $R,S$ be two regular expressions. The idea is that if $L(R) \neq L(S)$ then there is a word in $L(R) \Delta L(S)$ whose length is at most exponential in $|R| + |S|$ (where $|R|$ is the length of $R$). This puts your problem in coNPSPACE=PSPACE, since you can guess and verify such a word.

Indeed, once you convert $R$ and $S$ to (polynomial size) NFAs, you can keep track of the set of possible states in both NFAs, and so verify that a word is accepted by one or not the other. You also need your machine to terminate if it guessed wrong, so you need to limit the length of the word to exponential in $|R| + |S|$. Fortunately, counting up to $\exp(|R|+|S|)$ takes only a polynomial size counter.

It remains to show that if $L(R) \neq L(S)$ then there is an exponential size witness. Indeed, the DFA for $L(R) \Delta L(S)$ has exponential size: the DFAs for $L(R)$ and $L(S)$, constructed from the corresponding NFAs, have exponential size, and the product construction maintains this property for $L(R) \Delta L(S)$. Finally, it is known that if a DFA with $n$ states accepts some word, then it accepts some word of length less than $n$.

$\endgroup$
8
  • $\begingroup$ I appreciate this answer but after struggling with this more I'm still not making the connection between the algorithm to prove that R and S are equivalent and PSPACE. I have no idea how to figure out how analyze the space complexity of this algorithm (and the text I have isn't helping), and I also can't seem to think of a way to alter it to take up less space. $\endgroup$
    – Brandon G
    Apr 12, 2016 at 3:03
  • $\begingroup$ Well, unfortunately I can't help you any more without giving away the answer. $\endgroup$ Apr 12, 2016 at 4:21
  • $\begingroup$ Louis provided a helpful comment to your question, which fills in the gap in my hint. $\endgroup$ Apr 12, 2016 at 7:39
  • $\begingroup$ you can keep track of the set of possible states in both NFAs What do you mean exactly ? $\endgroup$ Aug 17, 2017 at 21:37
  • $\begingroup$ @HaskellFun The set of states the NFAs could be in at any point in time. $\endgroup$ Aug 17, 2017 at 21:55
1
$\begingroup$

A good account of this result is in the lecture notes of Dexter Kozen, although the original work of Meyer and Stockmeyer contains a refined space bounds. You may consult that version in Stockmeyer's thesis, proposition 4.11 and theorem 4.13, for instance.

For the part on showing that if the languages are inequivalent then the algorithm accepts it comes handy to use Theorem 10 of Rabin and Scott paper.

$\endgroup$

Your Answer

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

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