for all w ∈ Σ * . If, on the other hand, there exists some string w ∈ Σ * such that
or vice versa, then the states p and q are said to be distinguishable by a string w.
Clearly, two states are either indistinguishable or distinguishable.
Indistinguishability has the properties of an equivalence relation: If p and q are
indistinguishable and if q and r are also indistinguishable, then so are p and r,
and all three states are indistinguishable.
One method for reducing the states of a dfa is based on finding and
combining indistinguishable states. We first describe a method for finding pairs
of distinguishable states.
procedure: mark
1. Remove all inaccessible states. This can be done by enumerating all simple
paths of the graph of the dfa starting at the initial state. Any state not part of
some path is inaccessible.
2. Consider all pairs of states (p, q). If p ∈ F and q ∉ F or vice versa, mark the
pair (p, q) as distinguishable.
3. Repeat the following step until no previously unmarked pairs are marked. For
all pairs (p, q) and all a ∈ Σ, compute δ(p, a)= p a and δ (q, a) = q a . If the pair
(p a ,q a ) is marked as distinguishable, mark (p, q) as distinguishable.
We claim that this procedure constitutes an algorithm for marking all
distinguishable pairs.
Theorem 2.3
The procedure mark, applied to any dfa M =(Q, λ,δ,q 0 ,F), terminates and
determines all pairs of distinguishable states.
Proof: Obviously, the procedure terminates, since there are only a finite number
of pairs that can be marked. It is also easy to see that the states of any pair so
marked are distinguishable. The only claim that requires elaboration is that the
procedure finds all distinguishable pairs.