Pushdown automaton
= Pushdown automaton
{wiki}
= Nondeterministic pushdown automaton
{synonym}
A finite control equipped with an unbounded <stack>. A move reads one input symbol or the <empty word>, examines the top <stack> symbol, changes control state and replaces that top by a finite <word> over the <stack alphabet>. Nondeterministic choices give finitely many possible moves. With <acceptance by final state> and the entire input consumed, <pushdown automata> recognize exactly the <context-free languages>.