STIMULUS-RESPONSE THEORY OF FINITE AUTOMATA

The central aim of the paper is to state and prove a representation theorem for finite automata in terms of models of stimulus-response theory. The main theorem is that, given any connected finite automaton, there is a stimulus-response model that asymptotically becomes isomorphic to it. Implications of this result for language learning are discussed in some detail. In addition, an immediate corollary is that any tote hierarchy in the sense of Miller and Chomsky is isomorphic to some stimulus-response model at asymptote. Representations of probabilistic automata are also discussed, and an application to the learning of arithmetic algorithms is given. © 1969.