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

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

**supriyas**#1

**APU**#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.

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