Question 9743 – Theory-of-Computation
December 6, 2023Question 3234 – Research Aptitude
December 6, 2023Question 9744 – Theory-of-Computation
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
Correct Answer: B
Question 49 Explanation:
If NFA contains N, then possible number of states in possible DFA is 2N.
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
N2
2N
2N
N!