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