Converting NFA to DFA (exponential).

Question

I understand how to convert from an NFA to a DFA, and the if there are $n$ states in a NFA there will be $2^n$ states in the DFA (without minimizing). Would someone mind explaining the intuition behind this? Why does $n$ states become $2^n$? Essentially, there is an exponential blowup, but what is the reason to why this true?

Answer 1

Look at the construction: each set of states in the NFA becomes a single state in the DFA. A set of $n$ states has $2^n$ subsets, so if the NFA has $n$ states, the DFA will automatically have $2^n$ states, one for each subset of the state set of the NFA.

Answer 2

A different attempt at making the result intuitive:

Think of an NFA $M$ as a finite graph whose edges (transitions) are labelled with either $\varepsilon$ or a symbol of its alphabet. Recall what it means for an NFA $M$ to accept a string $s$: $M$ accepts $s\in\Sigma^*$ iff there is some path from $M$'s start state $q_0$ to one of its accepting states, such that $s$ is the result of concatenating all the labels of edges in the path.

For simplicity, let's assume that $M$ doesn't have any $\varepsilon$-transitions. It's easy enough to accommodate them in describing how $M$ behaves, but it requires more fuss, and anyway this assumption doesn't sacrifice generality as $\varepsilon$-transitions can be eliminated.

Where $Q$ is the set of states of $M$, we'll refer to subsets of $Q$ as state sets. Here's what $M$ does, on an input string $s$:

• $M$ starts in state set $\{q_0\}$.

• After scanning any prefix $w$ of $s$, $M$ is in some state set $X$, consisting of all states reachable from $q_0$ via a path labelled $w$. (This is basically an induction hypothesis.)

• On scanning the next symbol $c$ of $s$, $M$ will be in the state set consisting of every state reachable from a state in $X$ by a transition labelled $c$. (Inductively, then, the new state set will consist of all possible states that can be reached by paths from $q_0$ that are labelled $wc$.)

• After consuming all of $s$, $M$ accepts $s$ iff its final state set contains an accepting state.

So, you can think of an NFA $M$ as transitioning on each input symbol from one sets of states to another. The explicit construction of a DFA from an NFA just makes this idea precise. The states of the constructed DFA are precisely the "state sets" of the NFA, of which there are of course $2^n$ where $\lvert Q\rvert = n$.

Answer 3

It is so because each and every state in the NFA after the conversion gets expanded in the single state in the DFA. And since the set of states suppose $n$ is there so the number of subsets will be $2n$. So, with the same, the DFA will have $2^n$ states for every subset of the NFA.