Editing Pushdown automaton (section)

{{short description|Type of automaton}}
{{More citations needed|date=April 2022}}
{{Automata theory}}
In the [[theory of computation]], a branch of [[theoretical computer science]], a '''pushdown automaton''' ('''PDA''') is   
a type of [[Automata theory|automaton]] that employs a [[Stack (data structure)|stack]].

Pushdown automata are used in theories about what can be computed by machines. They are more capable than [[finite-state machine]]s but less capable than [[Turing machine]]s (see [[#Turing machines|below]]).
[[Deterministic pushdown automata]] can recognize all [[deterministic context-free language]]s while nondeterministic ones can recognize all [[context-free language]]s, with the former often used in [[parser]] design.

The term "pushdown" refers to the fact that the [[Stack (abstract data type)|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.<ref name="Hopcroft.Ullman.1967"/>
A [[nested stack automaton]] allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.