Question

We demonstrated that if A is recognized by a nondeterministic finite state automaton, it can be recognized by a deterministic finite-state automaton, by giving an algorithm for constructing a machine M' that is deterministic and accepts the same language as a nondeterministic machine M.
By the construction algorithm we used, how many states will M' have if M has n states. Justify your answer

Answer 1

If Non Deteterministic Finite Automaton for some language has n states, then states in Deteterministic Finite Automaton which accepts the same language as Non Deteterministic Finite Automaton can be determined by set of subsets of the states of the Non Deteterministic Finite Automaton.
Which means:-

1 ≤ states in equivalent Deteterministic Finite Automaton ≤ ,
where n is number of states in Non Deteterministic Finite Automaton.

For example if Non Deteterministic Finite Automaton has three states, and , then, Deteterministic Finite Automaton can have any number of states from the set:-

{{}, q0, q1, q2, {q0, q1}, {q1, q2}, {q0, q2}, {q0, q1, q2}}

So, corresponding DFA can have any number of stated from the above set i.e, number of states may be from as low as 0 to maximum of 8, if number of states in NFA is 3.