Below we shall consider finite automata only, although the majority of the results can easily be extended (with certain changes in terminology) to infinite automata too. Consider the decreasing series
A. A. Letichevskiĭ · 1965
ways have in mind ~ , sub-automata of the given automaton. Moreover, each automaton will be considered as the set (of states) on which (for each x E X) the transition function 6(a, x) = ax and the output function X(a, x) are given. This enables us to use set-theoretic operations on sub-automata of the given automaton. Consider some (non-initial) Mealy automaton A. Let the expression - b(a, b 6 A) mean that there exists word p 6 F(x) for the states and b such that ap = b (p can be empty). The relation - is the quasi-ordering relation on the set A. The relation ~ b and b - a is the equivalence relation. Equivalence classes with respect to this relation are called (automatic) layers of the automaton A. Thus, A is the union of nouintersecting layers. We shall give certain properties of the layers of A. Lets cAbealayer, a, b E S. Then: