Note first that states q i and q j are distinguishable with a string of length n if
and only if there are transitions for some a ∈ Σ, with q k and q i distinguishable by
a string of length n – 1. We use this first to show that at the completion of the nth
pass through the loop in step 3, all states distinguishable by strings of length n or
less have been marked. In step 2, we mark all pairs indistinguishable by λ, so we
have a basis with n = 0 for an induction. We now assume that the claim is true
for all i = 0,1,…, n – 1. By this inductive assumption, at the beginning of the nth
pass through the loop, all states distinguishable by strings of length up to n – 1
hd. Because of (2.5) and (2.6) above, at the end of this pass, all states
distinguishable by strings of length up to n will be marked. By induction then,
we can claim that, for any n, at the completion of the nth pass, all pairs
distinguishable by strings of length n or less have been marked.
and
To show that this procedure marks all distinguishable states, assume that the
loop terminates after n passes. This means that during the nth pass no new states
were marked. From (2. 5) and (2.6), it then follows that there cannot be any
states distinguishable by a string of length n, but not distinguishable by any
shorter string. But if there are no states distinguishable only by strings of length
n, there cannot be any states distinguishable only by strings of length n + 1, and
so on. As a consequence, when the loop terminates, all distinguishable pairs
have been marked.
The procedure mark can be implemented by partitioning the states into
equivalence classes. Whenever two states are found to be distinguishable, they
are immediately put into separate equivalence classes.
Example 2.15
Consider the automaton in Figure 2.18.
In the second step of procedure mark we partition the state set into final and
nonfinal states to get two equivalence classes {q 0 ,q 1 ,q 3 } and {q 2 ,q 4 }. In the next
and only if there are transitions for some a ∈ Σ, with q k and q i distinguishable by
a string of length n – 1. We use this first to show that at the completion of the nth
pass through the loop in step 3, all states distinguishable by strings of length n or
less have been marked. In step 2, we mark all pairs indistinguishable by λ, so we
have a basis with n = 0 for an induction. We now assume that the claim is true
for all i = 0,1,…, n – 1. By this inductive assumption, at the beginning of the nth
pass through the loop, all states distinguishable by strings of length up to n – 1
hd. Because of (2.5) and (2.6) above, at the end of this pass, all states
distinguishable by strings of length up to n will be marked. By induction then,
we can claim that, for any n, at the completion of the nth pass, all pairs
distinguishable by strings of length n or less have been marked.
and
To show that this procedure marks all distinguishable states, assume that the
loop terminates after n passes. This means that during the nth pass no new states
were marked. From (2. 5) and (2.6), it then follows that there cannot be any
states distinguishable by a string of length n, but not distinguishable by any
shorter string. But if there are no states distinguishable only by strings of length
n, there cannot be any states distinguishable only by strings of length n + 1, and
so on. As a consequence, when the loop terminates, all distinguishable pairs
have been marked.
The procedure mark can be implemented by partitioning the states into
equivalence classes. Whenever two states are found to be distinguishable, they
are immediately put into separate equivalence classes.
Example 2.15
Consider the automaton in Figure 2.18.
In the second step of procedure mark we partition the state set into final and
nonfinal states to get two equivalence classes {q 0 ,q 1 ,q 3 } and {q 2 ,q 4 }. In the next