Final answer:
If M is a nondeterministic finite automaton with n states, it is possible to construct a deterministic finite automaton equivalent to M with 2n states.
Step-by-step explanation:
The statement is True. If M is an n state nondeterministic finite automaton, it is possible to construct a deterministic finite automaton that is equivalent to M and has 2n states.
This can be done by using the powerset construction. The powerset construction converts a nondeterministic finite automaton (NFA) into an equivalent deterministic finite automaton (DFA) by considering the set of all possible states that the NFA could be in, which is a power set of the original set of states.
Each state in the resulting DFA corresponds to a subset of states in the original NFA. The size of the power set is 2^n, so the resulting DFA would have 2n states.