[Overview] [Previous] [Next]

# From NFA to DFA

Consider the following NFA:

What states can we be in (in the NFA) before reading any input? Obviously, the start state, A. But there is a transition from A to B, so we could also be in state B. For the DFA, we construct the composite state {A, B}.

State {A,B} lacks a transition for x. From A, x takes us to A (in the NFA), and the null transition might take us to B; from B, x takes us to B. So in the DFA, x takes us from {A,B} to {A,B}.

State {A,B} also needs a transition for y. In the NFA, (A,y)=C and (B,y)=C, so we need to add a state {C} and an arc y from {A,B} to {C}.

In the NFA, (C,x)=A, but then a null transition might or might not take us to B, so we need to add an arc x from {C} to {A,B}.

Also, there are two arcs from C labeled y, going to states B and C. So in the DFA we need to add the state {B,C} and the arc y from {C} to this new state.

In the NFA, (B,x)=B and (C,x)=A (and by a transition we might get back to B), so we need an x arc from {B,C} to {A,B}.

(B,y)=C, while (C,y) is either B or C, so we have an arc labeled y from {B,C} to {B,C}.

We now have a transition from every state for every symbol in . The only remaining chore is to mark all the final states. In the original NFA, B was a final state, so in the DFA, every state containing B is a final state.