Who first introduced the pushdown automaton?
$begingroup$
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?
pushdown-automata history
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
$endgroup$
add a comment |
$begingroup$
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?
pushdown-automata history
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
$endgroup$
$begingroup$
One possibility is S. GINSBURG, S. GREIBACH, AND M. HARRISON, "Stack Automata and Compiling." JACM 14, 172-201 (1967).
$endgroup$
– Yuval Filmus
5 hours ago
$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$
– templatetypedef
4 hours ago
add a comment |
$begingroup$
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?
pushdown-automata history
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
$endgroup$
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?
pushdown-automata history
pushdown-automata history
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
asked 5 hours ago
templatetypedeftemplatetypedef
5,53911843
5,53911843
$begingroup$
One possibility is S. GINSBURG, S. GREIBACH, AND M. HARRISON, "Stack Automata and Compiling." JACM 14, 172-201 (1967).
$endgroup$
– Yuval Filmus
5 hours ago
$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$
– templatetypedef
4 hours ago
add a comment |
$begingroup$
One possibility is S. GINSBURG, S. GREIBACH, AND M. HARRISON, "Stack Automata and Compiling." JACM 14, 172-201 (1967).
$endgroup$
– Yuval Filmus
5 hours ago
$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$
– templatetypedef
4 hours ago
$begingroup$
One possibility is S. GINSBURG, S. GREIBACH, AND M. HARRISON, "Stack Automata and Compiling." JACM 14, 172-201 (1967).
$endgroup$
– Yuval Filmus
5 hours ago
$begingroup$
One possibility is S. GINSBURG, S. GREIBACH, AND M. HARRISON, "Stack Automata and Compiling." JACM 14, 172-201 (1967).
$endgroup$
– Yuval Filmus
5 hours ago
$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$
– templatetypedef
4 hours ago
$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$
– templatetypedef
4 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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). [...]
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102948%2fwho-first-introduced-the-pushdown-automaton%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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). [...]
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
$endgroup$
add a comment |
$begingroup$
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). [...]
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
$endgroup$
add a comment |
$begingroup$
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). [...]
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
$endgroup$
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). [...]
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
edited 2 hours ago
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
answered 4 hours ago
Hendrik JanHendrik Jan
20.9k2565
20.9k2565
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102948%2fwho-first-introduced-the-pushdown-automaton%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
One possibility is S. GINSBURG, S. GREIBACH, AND M. HARRISON, "Stack Automata and Compiling." JACM 14, 172-201 (1967).
$endgroup$
– Yuval Filmus
5 hours ago
$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$
– templatetypedef
4 hours ago