A Census of Finite Automata

Abstract

A finite automaton may be thought of as a possible abstraction of a digital computer. Imagine a tape or sequence of letters from some alphabet being fed into a device with a finite number of internal states. When the device is in a particular state and receives an input letter, the system passes to another internal state and prints a letter on an output tape. This operation is continued until the entire input sequence has been processed.Both Harary (6) and Ginsburg (4) have focused attention on the previously unsolved problem of counting the number of equivalence classes of finite automata. In the present paper, this problem is solved completely by proving a variety of theorems about the enumeration of functions.