100 views
If NFA has 'n' states then how DFA can have 2^n  states. Please help me in understanding how this is true.

As per my understanding every DFA is NFA then how no of states can be more in DFA than nfa

Thanks
| 100 views

Correction: If a NFA has $n$ states, the DFA can have at most $2^N$ states.

This is because each state of the NFA can be a part of the DFA or not - thus we have two choices for each state and $n$ such choices to make, thus giving us $2^N$ states.

by Loyal (6.8k points)
selected

Every DFA is NFA.....

let us say NFA has N states

when we convert NFA to DFA

in worst case we get 2^N states in DFA

by Active (1.7k points)

+1 vote