# Understanding an example of an EXP-SPACE Problem

I am trying to understand the example given here of an EXP-SPACE time decision problem.

They write :

An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression)

Here is what I understand. Supposing I have some alphabet $$\Sigma = \{a,b,c...,z\}$$, then a regular expression is a pattern in order to specify the set of strings that belong to some language.

So for instance if I have two regular expressions, say

$$aa+a^{*}+bb^2$$ then any string that satisfies this expression is in $$L_1$$ (language 1),

$$abc$$ then any string that satisfies this expression is in $$L_2$$

Why does determining if these languages are the same in the worst case take exponential space. Further what is the size of the input ? I imagine it could be the sum of lengths of the two reg-expressions, but I am not sure.

Edit: If the Kleene star criterion is dropped, then I could see that we could simply create a set with all possible strings (the power set), and then compare the two sets, not sure about the input size however.

• Why is this problem EXPSPACE-hard? This requires a proof. Perhaps Wikipedia has a link to one. – Yuval Filmus Jan 31 at 4:18
• @YuvalFilmus right, and here it is: people.csail.mit.edu/meyer/rsq.pdf, I will read this and try and give a sketch in the next few days or so. – IntegrateThis Jan 31 at 5:23