patternMinor
Who first introduced the pushdown automaton?
Viewed 0 times
thewhopushdownintroducedfirstautomaton
Problem
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?
Solution
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). [...]
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). [...]
Context
StackExchange Computer Science Q#102948, answer score: 5
Revisions (0)
No revisions yet.