<p>According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does <em>not</em> generate all strings. So your problem is also PSPACE-complete.</p>

<p>Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct an NFA $B$ for $r$, and use the power set construction to virtually construct a DFA $C$ equivalent to $B$; we will not keep $C$ in memory, but we have oracle access to $C$ using only polynomial space. Now virtually construct a DFA $D$ for the symmetric difference of $A$ and $C$ using the product construction. This DFA accepts no strings (and so $L(A) = L(r)$) if there is no path from the starting state to an accepting state. Since reachability is in NL and $D$ has size $2^{\mathrm{poly}(n)}$, we can check whether $L(D) = \emptyset$ in $\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$, the latter equality due to Savitch's theorem.</p>

CC BY-SA 3.0
2013-01-04T03:33:48.697Z
Are you sure it's *in* PSPACE  (if not it would just be PSPACE-HARD)?  Or maybe it's enough to check all the strings of some polynomial length to see if the regexp and the DFA agree on all of them?  Is that obvious?  :-)
Neal Young
CC BY-SA 3.0
2013-01-04T05:01:38.993Z
Remember reachability is in NL, so even though the DFA corresponding to the regular expression is exponential, since oracle access to it is cheap, we can figure out whether the symmetric difference is empty or not in NPSPACE=PSPACE.
Yuval Filmus
CC BY-SA 3.0
2013-01-04T12:20:54.437Z
I don't see the hardness result. That is, how do you reduce the problem above to universality of regular expressions?
Markus
CC BY-SA 3.0
2013-01-04T16:45:37.740Z
Choose the DFA that accepts everything. To show hardness, you reduce REGULAR EXPRESSION NON-UNIVERSALITY to the problem in question.
Yuval Filmus
CC BY-SA 3.0
2013-01-04T19:04:00.667Z
@YuvalFilmus Thanks for the reference! You should probably add your first comment to your answer for completeness, in both meanings of the word :)
Lev Reyzin
CC BY-SA 3.0
2013-01-05T01:33:38.810Z
I think you could write your answer as a proof. It is mostly there anyway. I don't understand what "virtually construct" means though.
Vijay D
CC BY-SA 3.0
2013-01-05T06:15:03.537Z
By "virtually construct" I mean "provide an oracle for". You don't want to actually construct it since it takes exponential space. Making the proof formal is something I leave to the reader.
Yuval Filmus
CC BY-SA 3.0
2013-01-03T23:31:27.333Z
2013-01-04T20:03:54.073Z
2013-01-04T20:03:54.073Z
Yuval Filmus
<p>Inspired by <a href="https://cstheory.stackexchange.com/questions/14939/what-algorithms-exist-for-construction-a-dfa-that-recognizes-the-language-descri">this question</a>, I am curious about the following:</p>

<blockquote>
  <p>What is the worst-case complexity of checking whether a given DFA accepts the same
  language as a given regular expression?</p>
</blockquote>

<p>Is this known?  The hope would be that this problem is in P -- that there is an algorithm polynomial in the size of both.</p>

<automata-theory><lg.learning><regular-expressions><dfa>
The Cost of an Equivalence Query for DFA
Lev Reyzin
# The Cost of an Equivalence Query for DFA

(Asked by: username_0 on 2013-01-03)

Inspired by [this question](https://cstheory.stackexchange.com/questions/14939/what-algorithms-exist-for-construction-a-dfa-that-recognizes-the-language-descri), I am curious about the following:

> What is the worst-case complexity of checking whether a given DFA accepts the same
> language as a given regular expression?

Is this known? The hope would be that this problem is in P -- that there is an algorithm polynomial in the size of both.

**Tags:** automata-theory, lg.learning, regular-expressions, dfa

---

## 1 answers

### Answer by username_1 on 2013-01-03. Score: 16 | Accepted answer

According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does *not* generate all strings. So your problem is also PSPACE-complete.

Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct an NFA $B$ for $r$, and use the power set construction to virtually construct a DFA $C$ equivalent to $B$; we will not keep $C$ in memory, but we have oracle access to $C$ using only polynomial space. Now virtually construct a DFA $D$ for the symmetric difference of $A$ and $C$ using the product construction. This DFA accepts no strings (and so $L(A) = L(r)$) if there is no path from the starting state to an accepting state. Since reachability is in NL and $D$ has size $2^{\mathrm{poly}(n)}$, we can check whether $L(D) = \emptyset$ in $\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$, the latter equality due to Savitch's theorem.

> **Comments:**
> **username_2**: Are you sure it's *in* PSPACE  (if not it would just be PSPACE-HARD)?  Or maybe it's enough to check all the strings of some polynomial length to see if the regexp and the DFA agree on all of them?  Is that obvious?  :-)  
> **username_1**: Remember reachability is in NL, so even though the DFA corresponding to the regular expression is exponential, since oracle access to it is cheap, we can figure out whether the symmetric difference is empty or not in NPSPACE=PSPACE.  
> **username_3**: I don't see the hardness result. That is, how do you reduce the problem above to universality of regular expressions?  
> **username_1**: Choose the DFA that accepts everything. To show hardness, you reduce REGULAR EXPRESSION NON-UNIVERSALITY to the problem in question.  
> **username_0**: @YuvalFilmus Thanks for the reference! You should probably add your first comment to your answer for completeness, in both meanings of the word :)  
> **username_4**: I think you could write your answer as a proof. It is mostly there anyway. I don't understand what "virtually construct" means though.  
> **username_1**: By "virtually construct" I mean "provide an oracle for". You don't want to actually construct it since it takes exponential space. Making the proof formal is something I leave to the reader.  

---

