What is the minimum number of states in a non-deterministic finite automaton that accepts L


#1

Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L? [GATE 2010]
a)n-1
b)n
c)n+1
d)2n -1


#2

We need minimum n+1 states to build NFA that accepts all substrings of a binary string. For example, following NFA accepts all substrings of “010″ and it has 4 states.

image

Alternatively,

We need a state for counting the length. So, for length n we need n+1 states (one for length zero). We don’t need a reject state for larger strings as we have NFA and not DFA. So, totally n+1 states are required