Can Any NFA Be Converted to a DFA?

Yes. Every finite NFA has an equivalent DFA: one that accepts exactly the same strings. The standard method is called the subset construction (or powerset construction). It works by making a DFA state represent all the NFA states that might be active after reading an input prefix.

The conversion preserves the language, not the internal behavior of the machine. The NFA may have several possible paths for an input; the DFA records those possibilities together in a single state.

The subset construction

Let an NFA have state set $Q$, alphabet $\Sigma$, start state $q_0$, accepting states $F$, and transition function $\delta$. For each symbol, an NFA transition can lead to a set of states, so $\delta(q,a) \subseteq Q$.

The DFA’s states are subsets of $Q$. Its start state is $\{q_0\}$. From a subset $S$ and input symbol $a$, the DFA moves to the union of all NFA states reachable on $a$ from states in $S$:

$$\delta_D(S,a)=\bigcup_{q\in S}\delta(q,a).$$

A subset is accepting if it includes at least one accepting NFA state:

$$F_D=\{S\subseteq Q:S\cap F\ne\varnothing\}.$$

This rule captures the NFA’s acceptance condition: an input is accepted if at least one possible path ends in an accepting state. The DFA accepts when its tracked set contains such a state.

In principle, an NFA with $n$ states has $2^n$ subsets, including the empty set. In practice, you usually construct only subsets reachable from the start state. The empty subset, if reached, is a nonaccepting dead state: every input symbol takes it back to itself.

Worked example: recognizing a string containing ab

Consider an NFA over $\{a,b\}$ with states $q_0,q_1,q_2$. Its start state is $q_0$, and $q_2$ is accepting. The transitions are:

NFA state	On a	On b
$q_0$	$\{q_0,q_1\}$	$\{q_0\}$
$q_1$	$\varnothing$	$\{q_2\}$
$q_2$	$\{q_2\}$	$\{q_2\}$

The NFA can stay in $q_0$ while reading the input, and whenever it sees an a, it can also guess that this a begins the target substring. It then moves to $q_2$ if the next symbol is b. State $q_2$ loops on both symbols, so a match remains recognized. The NFA accepts exactly the strings containing ab.

Now name the reachable DFA subsets:

• $A=\{q_0\}$, the start state;
• $B=\{q_0,q_1\}$;
• $C=\{q_0,q_2\}$;
• $D=\{q_0,q_1,q_2\}$.

For example, from $A$ on a, the NFA transitions from $q_0$ to $\{q_0,q_1\}$, so the DFA goes to $B$. From $B$ on b, it collects the destinations from both states: $q_0$ leads to $q_0$, and $q_1$ leads to $q_2$. Thus the result is $\{q_0,q_2\}=C$.

The complete reachable DFA is:

DFA state	On a	On b	Accepting?
$A=\{q_0\}$	$B$	$A$	No
$B=\{q_0,q_1\}$	$B$	$C$	No
$C=\{q_0,q_2\}$	$D$	$C$	Yes
$D=\{q_0,q_1,q_2\}$	$D$	$C$	Yes

The accepting DFA states are exactly the subsets containing $q_2$. Although the NFA has three states and therefore eight possible subsets in total, only four subsets are reachable in this example.

What if the NFA has epsilon transitions?

An $\varepsilon$-NFA can change states without consuming an input symbol. In that case, use the epsilon-closure of a set: all states reachable from it using zero or more epsilon transitions.

Start the DFA in the epsilon-closure of the NFA’s start state. After taking transitions on a symbol, take the epsilon-closure of the resulting set as well. The accepting-state rule stays the same: a DFA subset is accepting if it contains an NFA accepting state. This adjustment still produces an equivalent DFA.

Common mistakes

• Taking just one NFA transition: If several destinations are possible, include all of them in the next subset.
• Marking a subset accepting only when all its states accept: The correct rule is “at least one.” NFA acceptance requires one successful path, not that every possible path succeeds.
• Forgetting the empty subset: If no NFA state can be reached on a symbol, the DFA needs a destination for that transition. The empty subset supplies it and loops to itself.
• Assuming the DFA must have the same number of states: The DFA can have more states—up to $2^n$ before unreachable states are removed. It may be minimized afterward without changing the language.

The subset construction applies to every standard finite NFA, including one with epsilon transitions. It establishes that NFAs and DFAs recognize the same class of languages: the regular languages.