3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ @YuvalFilmus Thank you for this information. I was not aware that said page exists. $\endgroup$
    – fuz
    Mar 11, 2013 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, 2013 at 3:01

1 Answer 1

6
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ Why the downvotes? $\endgroup$ Mar 11, 2013 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, 2013 at 1:26
  • $\begingroup$ @SimonS - of course, thank you. I edited. $\endgroup$
    – Shaull
    Mar 12, 2013 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, 2013 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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