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

GATE · 2010 · CS · Computer Science & IT

Let w be any string of length \(n\) in \(\{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\)?

A.
\(n - 1\)
B.
\(n\)
C.
\(n + 1 \)
D.
\(2^{n -1 }\)

Attempted by 359 students.

Show answer

Correct answer: C

The worked solution is available to enrolled students.

Video solution available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2