9
$\begingroup$

I have my own version of lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version also supports the generation of NFAs (Non-deterministic Finite Automaton) and of course I try to keep the automatons as small as possible.

My question thus is: what is the most optimal known upper bound on the number of states in the NFA that accepts the complement of another NFA? Of course going through the conversion to a DFA (Deterministic Finite Automaton) and then interchanging accepting and rejecting states, gives an exponential upper bound. Are there any better known upper bounds? Preferably polynomial or even linear of course.

If no better upper bound is known, has it been shown that for some family of languages the lower bound is exponential or otherwise super polynomial?

$\endgroup$

2 Answers 2

6
$\begingroup$

In the paper State Complexity of Concatenation and Complementation of Regular Languages by Jirásek, Jirásková, and Szabari (LNCS Volume 3317, 2005, doi 10.1007/978-3-540-30500-2_17) very precise bounds for complexities for complement on non-deterministic automata are obtained. We do not need full details, but the authors cite an earlier report by one of them, stating:

Theorem 2. For any positive integer $n$, there exists a binary NFA $M$ of $n$ states such that any NFA for the complement of the language $L(M)$ needs at least $2^n$ states.

So it seems there is no better bound for complementation than via deterministic automata. At least in general.

$\endgroup$
1
  • $\begingroup$ That was the answer I was afraid I was going to get. Ah well, no more sleepless nights. $\endgroup$ May 5, 2013 at 13:03
3
$\begingroup$

One of the classical ideas in automata theory is showing that going from an NFA to a complementing one involves an exponential blow-up. Here is one way to do it:

Consider the alphabet $\Sigma = \{ 0, 1\}$, and for every $n\geq 1$, consider the language $$L_n = \{ w\in \Sigma^*: w \text{ has an infix }u \in 0 \cdot (0\cup 1)^{n-1} \cdot 1 \cup 1 \cdot (0\cup 1)^{n-1} \cdot 0\}$$

Thus, $L_n$ consists of all words $w$ that contain two letters that are $n$-distant apart and are different. Clearly, $L_n$ can be recognized by an NFA $A_n$ of size $\theta(n)$ as follows. $A_n$ guesses when an infix $u$ in $0 \cdot (0\cup 1)^{n-1} \cdot 1 \cup 1 \cdot (0\cup 1)^{n-1} \cdot 0$ starts. Then, it remembers the first letter of $u$, and finally checks whether the $n$'th letter after is different than the one we remembered.

Now consider the complement language $\overline{L_n}$. It is not hard to see that $\overline{L_n} \cap \Sigma^{2n} = \{ u\cdot u: u\in \Sigma^n \}$. We show next that every NFA $B_n$ that recognizes $\overline{L_n}$ has at least $2^n$ states (intuitively this is true as $B_n$ has to remember the last $n$ letters read):

Assume towards contradiction that $B_n$ is an NFA that has strictly less than $2^n$ states and recognizes $\overline{L_n}$. Then, consider the words $x_1 = u_1\cdot u_1,x_2 = u_2\cdot u_2, \ldots, x_{2^n} = u_{2^n} \cdot u_{2^n}$, where $u_1, u_2, \ldots, u_{2^n} \in \Sigma^n$ are all words of length $n$ over $\Sigma = \{ 0, 1\}$. As for all $i\in [2^n]$, $x_i$ is accepted by $B_n$, and $|B_n| < 2^n$, it follows that there are $i\neq j \in [2^n]$ and two accepting runs in $B_n$ on $x_i$ and $x_j$, where both runs pass through the same state after reading the first $n$ letters. So we have two runs $r_i$ and $r_j$ of the form:

$$ r_i = q^i_0 \xrightarrow{u_i} q \xrightarrow{u_i} q^f_i$$ $$ r_j = q^j_0 \xrightarrow{u_j} q \xrightarrow{u_j} q^f_j$$

where $q^i_0$ and $q^j_0$ are intial states of $B_n$, and $q^f_i$ and $q^f_j$ are accepting states of $B_n$. Now one can take the runs $r_i$ and $r_j$ and obtain the following accepting run in $B_n $ from them:

$$ q^i_0 \xrightarrow{u_i} q \xrightarrow{u_j} q^f_j$$

So on the one hand, $u_i\cdot u_j \in L(B_n) = \overline{L_n}$, and on the other hand, as $u_i\neq u_j$, it follows that $u_i\cdot u_j$ has two letters that are $n$-distant apart and are different, and thus $u_i\cdot u_j \in L_n$ and we've reached a contradiction.

$\endgroup$
2
  • $\begingroup$ Thanks! this is a very clear and easy to understand proof. $\endgroup$
    – a3nm
    2 days ago
  • $\begingroup$ @a3nm You're welcome. $\endgroup$ yesterday

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.