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?

M

Mr. Dubey

🎓 Coach ⭐ 103.11K Points

📊 Theory of Computation and Compiler Design

Q. 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) 2n-1

💬 Discuss

✅ Correct Answer: (C) n+1

You must be Logged in to update hint/solution

💬 Discussion

📊 Question Analytics

👁️

749

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

93%

Success Rate