An Approach to a Unified Theory of Automata

In the past, and especially recently, people have been examining various species of automata, perhaps as models of the compiling and translating processes, or for the insights they lend to computation. A partial list includes the Turing machine, 1 pushdown automaton, 2 , 3 - 4 deterministic pushdown automaton, 5 counter machine, 0,7 stack automation, in all its forms, two-way, 8 one-way, 0 , 1 0 , 1 1 nonerasing, 12 deterministic and nondeterministic, the nested stack automaton, 13 and the time 1 4 , 1 5 and tape 1 0 , 1 7 , 1 8 bounded Turing machines. This list is not meant to be a complete survey of past writings, and more can be expected in the future. Many of the properties of each of the automaton classes mentioned are the same. For example, one would expect the set of languages accepted by each class to be closed under intersection with a regular set. Our plan is to propose a model of an automaton abstracting the common features of most of the models mentioned. We will define a class of automata to be a subset of the set of all such automata if it satisfies certain simple and physically meaningful closure properties. Then, from these closure properties, we will derive many of the common closure theorems which have been proven for the specific types of automata mentioned, and which, presumably, would be proven for future types. The basic model is shown in Fig. 1. It consists of a two-way input tape, with end markers, a finite control, and an infinite storage of unspecified structure, called the balloon.