2
$\begingroup$

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.

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

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$.

$\endgroup$
  • 1
    $\begingroup$ Omega Police: that's why you shouldn't use $2^{O(n)}$! $\endgroup$ – Raphael Feb 3 '16 at 14:17

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.