way that, after reading w, the equivalent dfa will be in a single state labeled
{q i ,q j ,…,q k }. Since for a set of |Q| states there are exactly 2 |Q| subsets, the
corresponding dfa will have a finite number of states.
Most of the work in this suggested construction lies in the analysis of the nfa
to get the correspondence between possible states and inputs. Before getting to
the formal description of this, let us illustrate it with a simple example.
Example 2.12
Convert the nfa in Figure 2.12 to an equivalent dfa. The nfa starts in state q 0 , so
the initial state of the dfa will be labeled {q 0 }. After reading an a, the nfa can be
in state q 1 or, by making a λ-transition, in state q 2 . Therefore, the corresponding
dfa must have a state labeled {q 1 ,q 2 } and a transition
δ({q 0 },a) = {q 1 ,q 2 }.
In state q 0 , the nfa has no specified transition when the input is b; therefore,
δ ({q 0 },b) = Ø.
A state labeled Ø represents an impossible move for the nfa and, therefore,
means nonacceptance of the string. Consequently, this state in the dfa must be a
nonfinal trap state.
Figure 2.12
We have now introduced into the dfa the state {q 1 ,q 2 }, so we need to find the
transitions out of this state. Remember that this state of the dfa corresponds to
two possible states of the nfa, so we must refer back to the nfa. If the nfa is in
state q 1 and reads an a, it can go to q 1 . Furthermore, from q 1 the nfa can make a
λ-transition to q 2 . If, for the same input, the nfa is in state q 2 , then there is no
{q i ,q j ,…,q k }. Since for a set of |Q| states there are exactly 2 |Q| subsets, the
corresponding dfa will have a finite number of states.
Most of the work in this suggested construction lies in the analysis of the nfa
to get the correspondence between possible states and inputs. Before getting to
the formal description of this, let us illustrate it with a simple example.
Example 2.12
Convert the nfa in Figure 2.12 to an equivalent dfa. The nfa starts in state q 0 , so
the initial state of the dfa will be labeled {q 0 }. After reading an a, the nfa can be
in state q 1 or, by making a λ-transition, in state q 2 . Therefore, the corresponding
dfa must have a state labeled {q 1 ,q 2 } and a transition
δ({q 0 },a) = {q 1 ,q 2 }.
In state q 0 , the nfa has no specified transition when the input is b; therefore,
δ ({q 0 },b) = Ø.
A state labeled Ø represents an impossible move for the nfa and, therefore,
means nonacceptance of the string. Consequently, this state in the dfa must be a
nonfinal trap state.
Figure 2.12
We have now introduced into the dfa the state {q 1 ,q 2 }, so we need to find the
transitions out of this state. Remember that this state of the dfa corresponds to
two possible states of the nfa, so we must refer back to the nfa. If the nfa is in
state q 1 and reads an a, it can go to q 1 . Furthermore, from q 1 the nfa can make a
λ-transition to q 2 . If, for the same input, the nfa is in state q 2 , then there is no