Synchronization and Decomposition of Finite Automata

摘要

An input sequence x synchronizes a finite automation A if the state of A after receiving x is independent of the state of A before receiving x. The automaton A is synchronizable if such a sequence x exists. The questions of synchronizability and properties of the set of synchronizing sequences, both for arbitrary and particular classes of automata, motivate much of the present work. The homing and distinguishing problems are briefly discussed, with references to some of the related published research. The set of tapes which synchronize a purely k-definite automaton is characterized. This characterization is shown to carry over, but with a quite different proof, to ultimate-definite automata; and it is shown that every ultimate-definite automaton is synchronizable. Synchronization of reverse ultimate-definite automata is investigated, and a characterization is obtained for the synchronizing sequences of a subclass of such machines. Zeiger's procedure for decomposing a finite automaton into a cascade of permutation-reset machines is reviewed. Several flaws in the procedure are illustrated by examples and then remedied. It is shown that an automaton A is definite if and only if any Zeiger decomposition of A is a cascade of reset machines. (Author)