Let W be any string of length n in {0, 1}*. Let L be the

Home » Theory of Computation » Theory of computation miscellaneous » Question

Let W be any string of length n in {0, 1}*. Let L be the set of all sub-strings of W. What is the minimum number of states in a non-deterministic finite automata that accept L?

1. n − 1
2. n
3. n + 1
4. 2^{n − 1}

Correct Option: C

L is the set of all substrings of w where w! {0,1}) Any string in L would have length 0 to n, with any no. of 1's and 0's The NDFA

Here n = 4
So to accept all the substrings the no. of states required are n + 1 = 4 + 1 = 5
Hence (c) is correct option.