Equivalence of NFAs and DFAs

Construct a DFA from a NFA

In this lesson, we will show how to convert a NFA to a DFA. Consider the language $L$ over $\{ a,b \}$, which consists of strings that end and begin with the same symbol, i.e., $L = \{ \textrm{all strings of length at least two that begin and end with the same symbol} \}.$

The NFA that accepts the language L is depicted in the figure below.

The key idea is that for each state we have a (possibly empty) set of states to track for every input symbol. The tree in the figure below illustrates how things can progress as we begin with the start state of the original NFA, $q_0$, and track all possible moves while reading the first three symbols of any input string. In this case, going three levels deep suffices to observe all the possible states for this language. Multiple transitions leaving a state with the same symbol appear in horizontally adjacent boxes in the figure below.

The symbol $a$ can reach either $q_1$ or $q_3$ from state $q_1$. We will combine these two states into a single, “composite” state, $\{q_1,q_3\}$. The same logic applies to states $q_2$ and $q_3$ when leaving state $q_2$ with a $b$, giving us the composite state $\{q_2,q_3\}$. See the figure below.

This tree suggests that five possible states suffice to process all possible movements: $q_0$, $q_1$, $q_2$, $\{q_1, q_3\}$, and $\{q_2,q_3\}$, giving the following equivalent DFA.

Whenever a composite state contains any accepting state from the original NFA, that state becomes an accepting state in the resulting DFA. Thus, both states containing $q_3$ in the figure above are accepting states.

It is usually easier to track multiple moves in a NFA with a transition table instead of a tree. This is a transition table for the NFA.