Difference between revisions of "Pushdown automaton"
Karl Jones (Talk | contribs) (Created page with "In computer science, a '''pushdown automaton''' (PDA) is a type of automaton that employs a stack. == Description == P...") |
Karl Jones (Talk | contribs) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 14: | Line 14: | ||
* [[Context-free grammar]] | * [[Context-free grammar]] | ||
* [[Counter automaton]] | * [[Counter automaton]] | ||
| − | * [[Finite | + | * [[Deterministic pushdown automata]] |
| + | * [[Finite-state machine]] | ||
* [[Stack (abstract data type)]] | * [[Stack (abstract data type)]] | ||
* [[Stack machine]] | * [[Stack machine]] | ||
Latest revision as of 15:47, 24 September 2016
In computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.
Description
Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines. Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design.
The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata.
A nested stack automaton allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.
See also
- Automata theory
- Context-free grammar
- Counter automaton
- Deterministic pushdown automata
- Finite-state machine
- Stack (abstract data type)
- Stack machine
External links
- Pushdown automaton @ Wikipedia
