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$

migrated from cstheory.stackexchange.com Mar 11 '13 at 21:55

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\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
4
$\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,...$ 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| 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$
  • 2
    $\begingroup$ Why the downvotes? $\endgroup$ – Yuval Filmus 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
  • $\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.