Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Pushdown automaton
open-in-new
<p>In the <a href="/facts/Theory_of_computation/xYJd2YeI">theory of computation</a>, a branch of <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, a pushdown automaton (PDA) is a type of <a href="/facts/Automata_theory/Q6BmPv63">automaton</a> that employs a <a href="/facts/Stack_(data_structure)/bj7l94v1">stack</a>. </p><p>Pushdown automata are used in theories about what can be computed by machines. They are more capable than <a href="/facts/Finite-state_machine/GMusWd0a">finite-state machines</a> but less capable than <a href="/facts/Turing_machine/ojCtglYu">Turing machines</a> (see below). <a href="/facts/Deterministic_pushdown_automata/WHaMPJcS">Deterministic pushdown automata</a> can recognize all <a href="/facts/Deterministic_context-free_language/XDlUnBJ8">deterministic context-free languages</a> while nondeterministic ones can recognize all <a href="/facts/Context-free_language/sHDxB5So">context-free languages</a>, with the former often used in <a href="/facts/Parser/nRKB01S3">parser</a> design. </p><p>The term "pushdown" refers to the fact that the <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack</a> 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 <a href="/facts/Nested_stack_automaton/cJ9K2ooD">nested stack automaton</a> allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols. </p>