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.