The question is in title. Let me repeat:

What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$

I feel both NFA and DFA will take following form:

enter image description here

and thus both have $n+1$ states. Am I correct with this? Or the DFA needs to take following form?

enter image description here

I feel its not necessary to have transitions defined for every symbol for every state, mainly because it does not eliminate "deterministic" nature of the automaton. Am I right?

up vote 1 down vote accepted

As mentioned in the other answer, there are two common definitions of DFA. One definition requires the transition function to be total, and the other allows it to be partial. The former one is somewhat more common.

Under the first definition, you need to include the additional state. Under the second definition, you don't have to.

Using Myhill–Nerode theory, it is easy to show that $n+2$ is the minimum number of states in a (total) DFA accepting the words of length between $0$ and $n$. Indeed, consider the words $\epsilon, 0, 0^2, \dots, 0^{n+1}$. These $n+2$ words are pairwise distinguishable. Indeed, if $0 \leq i < j \leq n+1$ then $0^j0^{n+1-j}$ doesn't belong to the language, but $0^i0^{n+1-j}$ does.

Using the "fooling set" method, it is easy to show likewise that $n+1$ is the minimum number of states in an NFA accepting the same language. Here is a statement of the method:

Let $L$ be a regular language. Suppose that there are $m$ pairs of words $x_i,y_i$ such that $x_iy_i \in L$ for all $i$, and for all $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. Then every NFA for $L$ contains at least $m$ states.

We choose $x_i = 0^i$ and $y_i = 0^{n-i}$ for $0 \leq i \leq n$, in total $n+1$ pairs. Clearly $x_i y_i = 0^n \in L$ (denoting our language by $L$), whereas for $i < j$, $x_j y_i = 0^{n-i+j} \notin L$.

You can define DFAs in both ways. One can require the transition function to be total, but it is indeed fine to define DFAs without this requirement. You (or your lecturer) just choose one definition and stick with it.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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