pushdown automaton

A pushdown automaton (PDA) is a type of automaton that employs a stack. They are more capable than finite-state automata but are less capable than Turing machines.

Pushdown automata have the same expressive power as context-free grammar. The languages recognized by PDAs is exactly the class of context-free languages. Formally, for every CFG, there is a PDA that recognize the same language, and vice versa.

Subtopics

• deterministic pushdown automaton

Visualization

Below is an example PDA for the language . The notation is similar to the graphs of finite automata, but we will write to mean the PDA consumes from the input and push to the stack.

Formalism

A pushdown automaton is a tuple where:

1. is the finite set of states
2. is the finite input alphabet
3. is the finite stack alphabet
5. is the initial state
6. is the set of final states

If the transition function takes a tuple of the form means that if the PDA is in state and , we consume the input, push to the stack, and change the state to . In case of , the effect is the same but no input symbol is read or consumed.

If the transition function takes a tuple of the form , everything is similar but we additionally check if is on top of the stack, and if it is we pop and perform the transition.

Finally, is like an ordinary NFA transition that doesn’t change the stack.

See Also

• stack machine