CHARACTERIZATION OF FINITE STATE AUTOMATA—TOPOLOGICAL APPROACH
Toshitami Nishikawa, Yasuhiko Takahara · International Journal of General Systems · 1992
This paper deals with the characterization problem or finite state automata. Firstly, two examples of automata are presented, one indicating the existence of some specific class of automata which is on the boundary between finite and infinite automata, and the other as a counterexample to a condition which has been speculated to characterize the finite state automaton class. Secondly, a metric called causal metric is defined for discrete time systems, and the concept of causality of general time systems is topologically characterized for discrete cases. Based on the causal metric another metric is defined on the state spaces of discrete time systems. The compactness of the state spaces with respect to the metric is discussed and this leads us to the theorem: A stationary, causal and finitely observable discrete lime system can be represented by and only by finite automata.