4 ms·
Combining a finite state machine for recognizing sentential patterns, with a stack, gives us LR parsing. But push-down automata are significant not only becaus
by kazinator 3y ago
Combining a finite state machine for recognizing sentential patterns, with a stack, gives us LR parsing.
But push-down automata are significant not only because they have practical uses in parsing, but because they represent a theoretical class. They are more powerful than finite automata, but are not Turing complete.
If, say, we use a push-down automaton to make a Boolean decision: does this input string fall into the to-be-recognized set, or not? then there are some kinds of strings it won't be able to decide, that a full Turing machine could decide.
The limitation of push down automata is a direct consequence of the stack discipline. There is only one stack, and when the stack is popped, information is thrown away.
The tape machine that Turing described as part of developing his theory of computation doesn't have that limitation; when the tape head moves backwards, material it has written to the tape is not erased in a stack-like discipline.
- mcguire 3y agoNeat observation: finite automata, push-down automata, and Turing machines can be distinguished purely by the number of stacks they need. Finite automata: no stack. Pushdown automata: one stack. Turing machine: two stacks. (Use them like the tape: to move forward, pop the f-stack and push the symbol on the b-stack; to move backward pop the b-stack and push to the f-stack.)
- mark_undoio 3y agoI think it's a shame this wasn't highlighted more explicitly in, at least, my computer science degree. We did finite state machines in quite a bit of detail, vaguely referred to pushdown automata but then concentrated on lambda calculus for quite a lot, with Turing machines less so. The Turing machine description, without showing it in this hierarchy, seems like a really weird abstraction. Fitting it in here (and combining it with the different Chomsky classes of grammar) makes it all feel more joined up.
- mcguire 3y agoThat was the way I learned it. I found the lambda calculus the odd one out. :-)
- eternityforest 3y agoWhat else can they do? Has anyone used them outside of parsing, as a way to satisfy the principle of least power?
- 082349872349872 3y agoMichael Jackson's single-threaded "Jackson Structured Programming"?