GATE 2008-IT
April 5, 2025GATE 2008-IT
April 5, 2025GATE 2008-IT
| Question 6 |
Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
| m ≤ 2n | |
| n ≤ m | |
| M has one accept state | |
| m = 2n |
Question 6 Explanation:
Set of states of NFA = n
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
Correct Answer: A
Question 6 Explanation:
Set of states of NFA = n
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n