Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the language is simply a matter of changing all accepting states into rejecting states and vice-versa. Are there any other things to conclude? Is there anything one can say about the number of states of a (minimal) NFA?

  • $\begingroup$ @YuvalFilmus Thank you for this information. I was not aware that said page exists. $\endgroup$
    – FUZxxl
    Mar 11 '13 at 17:01
  • $\begingroup$ one angle: it seems to be connected somewhat to set subtraction because set subtraction $A - B$ can be expressed as $A \cap \overline{B}$. which also has a connection to determining if $A \subset B$ $\endgroup$
    – vzn
    Mar 16 '13 at 3:01

Complementing an NFA may involve an exponential blowup.

While there are concrete examples for this, it can also be deduced (in a way) by the fact that NFA universality is PSPACE complete. Indeed, if complementing an NFA could be done in polynomial time, then universality would also be possible in polynomial time.

This is not exact, since complemetation could also be only sub-exponential, but not polynomial.

As for a concrete example: Let $p_1,p_2,\dots$ be an enumeration of the prime numbers. Consider the language: $L_k=\{1^n: \exists 1\le i\le k\ \text{ s.t. }\ p_i \not\mid n\}$. It is easy to construct an NFA for $L_k$ with $\sum_{i=1}^kp_i$ states.

However, it is also not hard to prove that a minimal NFA for $\overline{L_k}$ needs $\prod_{i=1}^k p_i$ states, which is exponential in $\sum_{i=1}^kp_i$.

  • 3
    $\begingroup$ Why the downvotes? $\endgroup$ Mar 11 '13 at 16:39
  • 1
    $\begingroup$ What's the $n$ for in $L_k$? Did you mean $L_k=\{1^n: \exists 1\le i\le k\ \text{ s.t}\ p_i \not| n\}$? $\endgroup$
    – Simon S
    Mar 12 '13 at 1:26
  • $\begingroup$ @SimonS - of course, thank you. I edited. $\endgroup$
    – Shaull
    Mar 12 '13 at 7:34
  • 1
    $\begingroup$ Is there construction, s.t. the complementary NFA is only constantly larger, while the minimal DFA has super polynomial size (both relative to the number of states of the original NFA)? $\endgroup$
    – frafl
    Mar 12 '13 at 11:01

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.