[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 empty string 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, delta(A,y)=C and delta(B,y)=C, so we need to add a state {C} and an arc y from {A,B} to {C}.

In the NFA, delta(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, delta(B,x)=B and delta(C,x)=A (and by a empty string transition we might get back to B), so we need an x arc from {B,C} to {A,B}.

delta(B,y)=C, while delta(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 sigma. 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.

Copyright © 1996 by David Matuszek
Last modified Jan 31, 1996