5
$\begingroup$

The wikipedia page Powerset construction says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input".

The smallest DFA for this (n+1)-states NFA according to Wikipedia.

I understand that the author wants to say that the smallest DFA equivalent to this NFA needs at least $2^n$ states.

But I can find a very much smaller DFA equivalent to this NFA just below:

A same size DFA equivalent to the NFA

Is Wikipedia wrong? Or am I? (which is much more likely)

$\endgroup$
10
$\begingroup$

The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000.

A DFA doesn't know how much input is left, so the property "the fourth character from the end" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each possible combination of the last four characters, so 2^4 states. If you look hard at the DFA the Wikipedia gives you should be able to figure out which of the states stores which combination of characters.

$\endgroup$
8
$\begingroup$

You can prove the lower bound on the number of states using Myhill-Nerode theory.

Suppose that we are given a language $L$, in this case the language over $\{0,1\}$ of words in which the $n$th last symbol is $1$. We say that two words $x,y$ (over the same alphabet) are equivalent if for all words $z$, $xz \in L$ iff $yz \in L$. It is easy to check that if two words $x,y$ are not equivalent, then $\delta(q_0,x) \neq \delta(q_0,y)$ for every DFA for $L$. In particular, if we can find $N$ pairwise inequivalent words, then it follows that every DFA for $L$ must contain at least $N$ states.

For our language $L$, I claim that the set of $2^n$ words of length exactly $n$ are pairwise inequivalent. Indeed, suppose that $x \neq y$ are two words of length $n$. Then $x_i \neq y_i$ for some $i$, say $x_i = 0$ and $y_i = 1$ (without loss of generality). Then $x0^{i-1} \notin L$ whereas $y0^{i-1} \in L$, since in both cases the $n$th symbol from the end is $x_i$ or $y_i$. Thus every DFA for $L$ must contain at least $2^n$ states.

$\endgroup$
  • $\begingroup$ Thanks for your contribution. Myhill-Nerode has always be unclear for me and your explanation is very easy to understand. $\endgroup$ – Luz Jan 16 '17 at 13:29

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.