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?