Show Recognizing two Regular Expressions as equal is in PSPACE
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$ steps accepts some word, then it accepts some word of length less than $n$.