specified transition. Therefore,
δ({q 1 ,q 2 },a) = {q 1 ,q 2 }.
Similarly,
δ({q 1 ,q 2 },b) = {q 0 }
At this point, every state has all transitions defined. The result, shown in
Figure 2.13, is a dfa, equivalent to the nfa with which we started. The nfa in
Figure 2.12 accepts any string for which δ * (q 0 ,w) contains q 1 . For the
corresponding dfa to accept every such w, any state whose label includes q 1 must
be made a final state.
Figure 2.13
Theorem 2.2
Let L be the language accepted by a nondeterministic finite accepter M N = (Q N ,
Σ,δ N ,q 0 ,F N ). Then there exists a deterministic finite accepter M D = (Q D , Σ,δ D ,
{q 0 },F D ) such that
L= L (M D ).
Proof: Given M N , we use the procedure nfa-to-dfa below to construct the
transition graph G D for M D . To understand the construction, remember that G D
δ({q 1 ,q 2 },a) = {q 1 ,q 2 }.
Similarly,
δ({q 1 ,q 2 },b) = {q 0 }
At this point, every state has all transitions defined. The result, shown in
Figure 2.13, is a dfa, equivalent to the nfa with which we started. The nfa in
Figure 2.12 accepts any string for which δ * (q 0 ,w) contains q 1 . For the
corresponding dfa to accept every such w, any state whose label includes q 1 must
be made a final state.
Figure 2.13
Theorem 2.2
Let L be the language accepted by a nondeterministic finite accepter M N = (Q N ,
Σ,δ N ,q 0 ,F N ). Then there exists a deterministic finite accepter M D = (Q D , Σ,δ D ,
{q 0 },F D ) such that
L= L (M D ).
Proof: Given M N , we use the procedure nfa-to-dfa below to construct the
transition graph G D for M D . To understand the construction, remember that G D