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$ 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
    Oct 21, 2013 at 19:15
  • $\begingroup$ @EmilJeřábek $\{0\}\cdot b = \emptyset$. $\endgroup$
    – J.-E. Pin
    Aug 6, 2022 at 8:36
  • $\begingroup$ Sorry, you are right; I didn’t notice that $(0,b,0)$ was missing. $\endgroup$ 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$ Aug 31, 2012 at 21:06
  • $\begingroup$ Thanks for the answer! What do you mean by co-NFA? $\endgroup$
    – mrk
    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$ 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$ Sep 1, 2012 at 6:24
  • $\begingroup$ Finite languages are somewhat boring in this regard. See also here. $\endgroup$
    – Raphael
    Sep 1, 2012 at 11:06

Your Answer

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

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