Pushdown automata

A pushdown automaton, or PDA, is finite automaton supplemented with a storage device, specifically, a stack onto which we can push symbols.

The transitions in the pushdown automaton read input symbols, just as a finite automaton does. Additionally, transitions can include stack operations that pop symbols from the top of the stack and/or push new symbols onto the stack.

Here is a typical transition in a PDA.

The transition has two parts: the symbol to be read from the input, and the stack operation. The stack operation has two parts: the symbol to be removed from the top of the stack and the symbol to be pushed onto the stack. The PDA can do the transition if and only if the required symbol come in on the input and the symbol that we want to remove the stack is sitting at the top of the stack. If either of these two requirements is missing, the machine can not do the transition.

PDAs also have the ability to ignore the input or the stack on a given transition. For example, to read a symbol from the input and simultaneously ignore the stack we do

The ε symbol in the stack part of the transition means "do nothing". In this example, we try to pop nothing from the stack and we push nothing on the stack.

To push a symbol on the stack without popping anything we do

To pop a symbol without pushing anything we do

At the start of the machine run the stack is empty. Depending on the requirements of the program, we may or may not also require that the stack be empty at the end of the input.

The stack alphabet

The set of symbols a PDA can use with the stack is known as the stack alphabet, Γ. Typically, the stack alphabet consists of the input alphabet Σ supplemented with additional marker symbols that play special roles in the machine.

One commonly used marker symbol, $, is used to mark the bottom of the stack. In many examples we start by placing a $ onto the stack at the very beginning of the run. The $ serves as a special marker to let us know whether or not the stack is about to empty out. When the $ reappears at the top of the stack we know that the stack is almost empty.

An example

The following PDA is designed to accept the language

L = { 0ⁿ1ⁿ | n > 0 }

PDAs are inherently nondeterministic

By definition, PDAs are nondeterministic machines. Many important PDA examples make essential use of nondeterminism.

Here is one famous example. The PDA below accepts the language

L = { ww^R | w ∈ Σ^* }

The machine uses the transition from state 2 to state 3 to guess when it has reached the middle of the input. The stack operations in states 2 and 3 enforce the constraint that the first half of the string in reverse order has to match the second half of the string.

Formal definition

A pushdown automaton is a 6-tuple (Q, Σ, Γ, δ, q₀, F) where Q, Σ, Γ, and F are all finite sets, and

1. Q is the set of states,
2. Σ is the input alphabet,
3. Γ is the stack alphabet,
4. δ: Q × Σ_ε × Γ_ε → P(Q × Γ_ε) is the transition function,
5. q₀ ∈ Q is the start state, and
6. F ⊆ Q is the set of accept states.