2
$\begingroup$

Hello for a homework I have to show that deciding whether a regex over $\Sigma = \{0,1\}$ descibes $\Sigma^*$ is $\mathsf{coNP}$ complete (this is irrelevant for the question though).

The thing which irrs me is that I think this problem is in $\mathsf{P}$.

Here is my argumentation:

Let $R$ be a regex, then we have $$L(R) = \{0,1\}^* \Leftrightarrow \overline{L(R)} = \varnothing$$

Given $R$ we can consruct an NFA with $\epsilon$ moves for $L(R)$ in poly. time; eliminating the $\epsilon$ moves (again poly. time: $O(|Q| \cdot |\delta| \cdot |\Sigma|)$) we obtain an NFA $M$.

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline {L(R)}$, whose emptiness we can check with a BFS (again in poly. time).

$\leadsto \mathsf{RegExpEq_{*}} \in \mathsf{P}$

Where does my argumentation shatter? If both my argumentation and the question is correct, then $\mathsf{P} = \mathsf{coNP}$ which seems highly doubtful.

$\endgroup$
7
$\begingroup$

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline{L(R)}$.

Well, that's not true. You won't get $\overline{L(R)}$. That would have happened if $M$ was a DFA, rather than a NFA. So you have to first convert $M$ to $M'$ which is a DFA, but then you would have to spend an exponential time there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.