Definition A.6
Two states q i and q j are said to be k-equivalent
for all |w| ≤ k. Two states are k-distinguishable if there exists a |w| ≤ k such that
.
Theorem A.4
(a) Two states q i and q i of a Mealy machine are 1-distinguishable if there exists
an a ∈ ∑ such that
(b) The two states are k-distinguishable if they are (k – 1)-distinguishable or if
there is an a ∈ ∑ such that
where q r and q s are (k – 1)-distinguishable.
Proof: Part(a) follows directly from the definition and so does the conclusion
that states are k-distinguishable if they are (k – 1)-distinguishable. For Part (b),
we know that there exists a |w| ≤ k – 1, such that
Now
and
The result then follows.