9
$\begingroup$

How can I build an example of a DFA that has $2^n$ states where the equivalent 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$
  • $\begingroup$ This question is somewhat unclear. In general, there are infinitely many equivalent DFAs for any given regular language, and infinitely many equivalent NFAs for any given regular language. If you want minimal DFAs with $2^n$ states, this isn't always even possible, since different NFAs can recognize the same language and have different numbers of states, but correspond to the same minimal DFA. If, additionally, you want only to consider "minimal" NFAs, this becomes somewhat more interesting... $\endgroup$ – Patrick87 Aug 31 '12 at 22:25
  • 1
    $\begingroup$ Patrick, I think the OP means an example where the minimal DFA is exponentially larger than the minimal NFA. $\endgroup$ – Yuval Filmus Sep 1 '12 at 6:25
  • $\begingroup$ @Patrick87 I'm not looking for an algorithm. All I want is an example of a pair of machines: DFA with $2^n$ states and NFA with $n$ states accepting the same language. $\endgroup$ – saadtaame Sep 1 '12 at 7:22
  • $\begingroup$ @saadtaame: That's trivial: take any DFA and add enough states to reach $2^n$. Interesting example are those where the minimal equivalent DFA has as many states. $\endgroup$ – Raphael Sep 1 '12 at 11:03
  • 1
    $\begingroup$ Note that the Wikipedia article on DFA minimisation references suitable examples (although you have to figure out the small NFA yourself). $\endgroup$ – Raphael Sep 1 '12 at 11:11
17
$\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$
10
$\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$
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$
  • $\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$ – saadtaame 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
7
$\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-1\} \cup \{(n-1, a, 0)\} \cup \{(i, b, i) \mid 1 \leqslant i \leq 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$
  • 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
  • 2
    $\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

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.