Show Recognizing two Regular Expressions as equal is in PSPACE

Question

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?

Answer 1

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

Answer 2

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.