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?


4 Answers 4


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

  • 4
    $\begingroup$ 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. $\endgroup$ Commented Oct 21, 2013 at 18:40
  • 3
    $\begingroup$ @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. $\endgroup$
    – J.-E. Pin
    Commented Oct 21, 2013 at 19:15
  • $\begingroup$ @EmilJeřábek $\{0\}\cdot b = \emptyset$. $\endgroup$
    – J.-E. Pin
    Commented Aug 6, 2022 at 8:36
  • $\begingroup$ Sorry, you are right; I didn’t notice that $(0,b,0)$ was missing. $\endgroup$ Commented Aug 6, 2022 at 9:06

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.


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.

  • $\begingroup$ Also, the proof of the second part "requires" communication complexity, so this might not be suitable for your purposes. $\endgroup$ Commented Aug 31, 2012 at 21:06
  • $\begingroup$ Thanks for the answer! What do you mean by co-NFA? $\endgroup$
    – mrk
    Commented Aug 31, 2012 at 21:22
  • $\begingroup$ 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. $\endgroup$ Commented Aug 31, 2012 at 21:28
  • $\begingroup$ 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. $\endgroup$ Commented Sep 1, 2012 at 6:24
  • $\begingroup$ Finite languages are somewhat boring in this regard. See also here. $\endgroup$
    – Raphael
    Commented Sep 1, 2012 at 11:06

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.