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.

Copyright © 1996 by David Matuszek

Last modified Jan 31, 1996