Characterization of Finite State Automaton

No one has ever successfully given a satisfactory characterization of a finite automaton, that is, no complete answer has been given to the problem to determine whether a system given by its input-output behavior is realizable as a finite automaton. Gill and Heun studied the problem under the condition that an input and output sequence is finite. This paper treats the problem in a general framework and gives a sufficient condition for a set of input and output sequences to be realized by a finite automaton. Specifically, the paper shows that if a system has finite input and output alphabets and if it is stationary and past-determined, it is realizable as a finite automaton. The paper also clarifies the relation between the result of this paper and that of Gill.