# Regex to NFA to complement

So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear.

Now to go from that NFA to the complement of the NFA, since I can't just flip accept and reject states, this means turning the NFA into a DFA.

If $n$ is the number of states in the NFA, the DFA simulating the NFA can have $2^n$ states.

So would the process of regex to NFA to complement of the NFA be $O(2^n)$?

Trying to figure out what big-O notation it would be.

• Are you asking if it can be in $\Omega(2^n)$? – Raphael Feb 3 '16 at 14:16

No. As you said, the NFA can have $m=O(n)$ states, and the DFA can have as many as $2^m$ states, so the DFA can have as many $2^{O(n)}$ states. Consequently, converting a regexp to a NFA and then complementing the NFA can yield an automaton with $2^{O(n)}$ states. $2^{O(n)}$ is larger than $O(2^n)$: notice the difference between $2^{cn}$ vs $c \cdot 2^n$.
• Omega Police: that's why you shouldn't use $2^{O(n)}$! – Raphael Feb 3 '16 at 14:17