The stack and pushdown automatons

Pushdown automatons

Pushdown automatons

In a finite-state machine the action of the machine depends on the state, and on the input. In a pushdown automaton it also depends on a third input – stack.

In addition, in addition to changing the state, it can also pop the stack, or push to the stack.

The stack is a list of symbols. It is the first item on the stack which is used to inform the decision.

A pushdown automaton uses a Last-in First-out (LiFo) stack.