I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble finding a source that first introduces pushdown automata. Who first developed them, and what was the context?
-
$\begingroup$ One possibility is S. GINSBURG, S. GREIBACH, AND M. HARRISON, "Stack Automata and Compiling." JACM 14, 172-201 (1967). $\endgroup$– Yuval FilmusJan 16, 2019 at 18:48
-
$\begingroup$ @YuvalFilmus I had started off with that paper, but the opening paragraph begins by discussing pushdown automata as though the reader is already familiar with them. $\endgroup$– templatetypedefJan 16, 2019 at 18:54
1 Answer
Ginsburg (in his book The Mathematical Theory of Context-Free Languages, McGraw-Hill, 1966) states in the Historical References (Section 2.7, page 81):
Pushdown acceptors were first formalized by Chomsky [Ch5] and Evey [Ev], although the notion of a pushdown tape has been used since 1954.
[Ch5] N.Chomsky, context-free grammars and pushdown storage, MIT Res. Lab. Electron. Quart. Prog. Rept. 65, 1962.
[Ev] R.J.Evey, The theory and applications of pushdown store machines, Mathematical Linguistics and Automatic Translation, Harvard Univ. Computation Lab. Rept. NSF-IO, May, 1963.
The context can be read from the Preface of the same book.
The concept of a context-free language was first introduced by Chomsky in 1959 in an attempt to find a reasonable mathematical model of natural language such as English, French, etc. In the period 1959-1960, several papers developing the theory were written. In the late 1960, it was discovered that the "ALGOL-like" languages, that is, the languages defined by Backus normal form (the metalanguage used to describe the widely publicized programming language ALGOL-60), where identical with the context-free languages. Since then, there has been a flurry of activity in the theoretical development of context-free languages. Much of this work has been done by those concerned either with natural languages in connection with computers, or with programming languages. The remainder has been by mathematicians and logicians intrigued by the inherent problems, techniques, and results. This activity has been given birth to a number of theoretical results of concern to computer science, and especially to programming technology. For example, we have the characterization of a context-free language in terms of a pushdown acceptor (a device used in the parsing aspect of compiling). [...]