On the distinguishability of states of automata

We investigate variants of the notion of distinguishability of automata. The distinguishability in the sense of a given metric on the set of output symbols, the $k$-distinguishability and the $\infty$-distinguishability are considered. For each variant the exact value of the corresponding Shannon function is obtained. We find the minimum value of the parameter $k$ for which the $k$-distinguishability implies the $\infty$-distinguishability.
The research was supported by the Russian Foundation for Basic Research, grant 02–01–00162.