Let w be any string of length \(n\) in \(\{0, 1\}^*\). Let \(L\) be the set of…

PYQ GATE 2010

Let w be any string of length nn in {0,1}∗\{0, 1\}^*. Let LL be the set of all substrings of ww. What is the minimum number of states in a non-deterministic finite automaton that accepts LL?

  1. A.

    n−1n - 1

  2. B.

    nn

  3. C.

    n+1n + 1

  4. D.

    2n−12^{n -1 }

Attempted by 457 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…