# NFA with exponential number of states when determinized

How can I build an example of a regular language where the minimal DFA has $$2^n$$ states and the minimal NFA has $$n$$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's state-set, but I don't know how to start. Any suggestions to put me on the right track?

The standard example is the language $L$ of all words over an alphabet $A$ of size $n$ that don't contain all the different letters. There is an NFA accepting $L$ with $n+1$ states (or $n$ states if you allow multiple starting states): first guess a letter $a$ which is missing, then go (with an $\epsilon$-move) to an accepting state with self-loops for all letters other than $A$.

Any DFA for $L$ requires at least $2^n$ states. This can be seen using the Myhill-Nerode theorem. Let $S_1,S_2$ be two different subsets of $A$, and $w(S_1),w(S_2)$ words which contain all and only the letters in $S_1,S_2$, respectively. Without loss of generality, suppose $a \in S_1 \setminus S_2$, and let $w = w(A-a)$. Then $w(S_1)w \notin L$ while $w(S_2)w \in L$.

this is an exercise in the book "Finite Automata" by Mark V. Lawson Heriot-Watt University, Edinburgh, page 68:

Let $n \geq 1$. Show that the language $(0+1)^\ast 1(0+1)^{n−1}$ can be recognised by a non-deterministic automaton with $n+1$ states. Show that any deterministic automaton that recognises this language must have at least $2^n$ states. This example shows that an exponential increase in the number of states in passing from a non-deterministic automaton to a corresponding determin- istic automaton is sometimes unavoidable.

This is a late answer, but apparently nobody gave the optimal solution. Take $$A = \{a, b\}$$, $$Q_n = \{0, 1, \ldots, n-1\}$$ et $${\cal A}_n = (Q_n, A, E_n, \{0\}, \{0\})$$, with $$E_n = \{(i, a, i+1) \mid 0 \leqslant i \leqslant n-2\} \cup \{(n-1, a, 0)\} \cup \{(i, b, i) \mid 1 \leqslant i \leqslant n-1\} \cup \{(i, b, 0) \mid 1 \leqslant i \leqslant n-1\}$$ This NFA on a two-letter alphabet has $$n$$ states, only one initial and one final states and its equivalent minimal DFA has $$2^n$$ states.

• Very clever! The language accepted by this automaton is $(a^n + aW_{n-1}b)^*$, where $W_{n-1}$ consists of all words containing the letter $a$ at most $n-1$ times. – Yuval Filmus Oct 21 '13 at 18:40
• @yuval-filmus This example is not mine. I wanted to give a reference, but at the moment I don't remember where I saw it. – J.-E. Pin Oct 21 '13 at 19:15

I'm going to guess that you mean that the optimal DFA has $2^n$ states. Maybe this doesn't get you $2^n$ states, but it's $\Omega(2^n)$.

From "Communication Complexity" by Kushilevitz and Nisan in exercise 12.6:

"For some constant [non-negative integer] $c$, consider the (finite) language $L_c = \{ww\mid w \in \{0,1\}^c\}$."

and the book continues on asking you to prove that you can find a co-NFA recognizing $L_c$ that uses $O(c)$ states and also that you cannot do better than $\Omega(2^c)$ states for a DFA.

• Also, the proof of the second part "requires" communication complexity, so this might not be suitable for your purposes. – Timothy Sun Aug 31 '12 at 21:06
• Thanks for the answer! What do you mean by co-NFA? – mrk Aug 31 '12 at 21:22
• Basically, switch "accepting" with "rejecting" in the definition of an NFA. That is, if none of the possible paths lead to a rejecting state, you accept, otherwise you reject. – Timothy Sun Aug 31 '12 at 21:28
• In fact, the $2^c$ lower bound follows quite easily from Myhill-Nerode. (In fact, you can get something like $(c+1)2^c$.) But my co-NFA uses $\Theta(c^2)$ states. – Yuval Filmus Sep 1 '12 at 6:24
• Finite languages are somewhat boring in this regard. See also here. – Raphael Sep 1 '12 at 11:06