Establishing certain bounds concerning finite automata

摘要

In this paper we establish a number of bounds concerning reduced finite-state machines. In particular, we prove that the least upper bound, L, on the length of synchronizing sequences is bounded byDownload : Download full-size imagewhere n is the number of states. We also prove that there exists a machine with a fixed number of inputs and outputs which is information lossless of maximal order. Finally we prove that for every n there exists a machine that is definitely diagnosable (or observable) of order μ = n(n − 1)/2.