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? A)n-1 B)n C)n+1 D)2^n-1

Question

Quizplus · Accepted Answer

A non-deterministic finite automaton (NFA) that accepts all substrings of a string of length n can be constructed with n+1 states. This is because for a string of length n, we need a state to represent the start of the string (before any character is read), and for each character in the string, we need a state to represent having read that character. This gives us a total of n+1 states, where transitions between states represent reading characters from the input string, and any state can transition to itself or any later state on reading a character, allowing the NFA to accept any substring of the original string.

Let W Be Any String of Length N Is {0,1}