Project ForgeTheory of Computation
Finite Automata & Regular Languages
GATE 2010
Hard
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?
- An-1
- Bn
- n+1
- D2^(n-1)
Explanation
The standard 'factor automaton' construction uses a simple linear chain of n+1 states representing every position 0..n along w, with nondeterministic transitions letting a substring match start at any position and every state marked accepting — exactly n+1 states.
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.