Machines, Programs and Languages
Eugene S. Santos†. · Journal of Cybernetics · 1974
Recently, several unifying schemes have been presented by various authors [1, 3, 4, 5] for the study of automata and formal languages. Among the various approaches, the one which deals with the concept of machines with standard input/output, introduced by Scott [5], seems to be the simplest and the most natural. Unfortunately, as it stands, machines with standard input/output are essentially one-way devices, and hence fail to encompass such machines as the two-way stack automata. In the present paper, we extend the concept to two-way machines. This provides a general framework for the study of the various two-way as well as one-way devices, deterministic or otherwise, which appeared in the literature.