11
$\begingroup$

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?

$\endgroup$
2
21
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\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$ – Yuval Filmus Oct 21 '13 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 '13 at 19:15
10
$\begingroup$

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.

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

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.