On the finite automata with maximal degree of state distinguishability

We consider a bound on one of the parameters of finite automata the degree of distinguishability. In the paper we consider sets of finite automata with arbitrary output and transition functions. The states of finite automata are called r-equivalent if the corresponding automata functions are equal on the words of length r. The states are called r-distinguishable if they are (r - 1)-equivalent and the corresponding automata functions are distinguishable on words of length r. The maximal degree of distinguishability of an automaton is called its degree of distinguishability. In the case of no restrictions there is a well-known attainable upper bound on the degree of distinguishability equal to s-1, wheres is the number of automaton states. A finite automaton defines in each of its states the function with domain (codomain) equal to the input (output) alphabet. We call the number of different such function the static functionality of the automaton. We consider finite automata with a given static functionality. We obtain an attainable upper bound on the degree of distinguishability equal to $s + 1 - F$ , where $F$ is the static functionality of the automaton. We call the set $\{s1, s2, . . . , s_F\}$ the finite automaton spectrum, where $s_i$, $1 \le i \le F$ , is the cardinality of the i-th 1-equivalence class. We show a relation between the maximal degree of distinguishability of finite automaton states and its spectrum.