Question 12976 – Operating-Systems
March 20, 2024Question 15156 – DSSSB TGT 2021
March 21, 2024GATE 2018
| Question 24 |
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
| k ≥ 2n | |
| k ≥ n | |
| k ≤ n2 | |
| k ≤ 2n |
Question 24 Explanation:
The number of states in DFA is always less than equal to 2no. of states in NFA.
In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2n states.
Hence k ≤ 2n is necessarily true.
In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2n states.
Hence k ≤ 2n is necessarily true.
Correct Answer: D
Question 24 Explanation:
The number of states in DFA is always less than equal to 2no. of states in NFA.
In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2n states.
Hence k ≤ 2n is necessarily true.
In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2n states.
Hence k ≤ 2n is necessarily true.