step, when we compute
δ(q 0 ,0) = q 1
and
δ(q 1 ,0) = q 2 ,
we recognize that q 0 and q 1 are distinguishable, so we put them into different
sets. So {q 0 ,q 1 ,q 3 } is split into {q 0 } and {q 1 ,q 3 }. Also, since δ(q 2 ,0) = q 3 and
δ(q 4 , 0) =q 4 , the class {q 2 ,q 4 } is split into {q 2 } and {q 4 }. The rest of the
computations show that no further splitting is needed.
Figure 2.18
Once the indistinguishability classes are found, the construction of the
minimal dfa is straightforward.
procedure: reduce
Given a dfa M = ( Q,Σ,δ, q 0 , F), we construct a reduced dfa
as
follows.
1. Use procedure mark to generate the equivalence classes, say {q i ,q j ,…,q k }, as
described.
2. For each set {q i ,q j ,…,q k } of such indistinguishable states, create a state
labeled i j…k for .