Pushdown Automata

Finite-state control with a stack

From finite automata to pushdown automata

A finite automaton has a fixed amount of memory encoded in its state. A pushdown automaton (PDA) augments finite-state control with a stack whose depth can grow with the input.

This single addition allows a PDA to recognize patterns that require unbounded nesting or matching, including:

$\{a^nb^n:n\ge0\}$;
balanced parentheses or braces;
strings of the form $w\#w^R$; and
palindromes.

A pushdown automaton combines finite-state control with stack operations.

The stack is deliberately restricted:

the machine may inspect only its top symbol;
it may push a symbol onto the top;
it may pop the top symbol; and
it cannot directly inspect symbols deeper in the stack.

This last-in, first-out memory is less flexible than the general memory of a Turing machine, but more powerful than finite state alone.

PDA overview

A PDA has:

a finite set of states;
a finite input alphabet;
a finite stack alphabet;
a transition relation, usually nondeterministic;
a start state; and
an acceptance condition.

There are two standard acceptance conventions:

Acceptance by final state: after consuming the entire input, at least one computation is in an accepting state.
Acceptance by empty stack: after consuming the entire input, at least one computation has emptied its stack.

These conventions recognize the same class of languages. A construction can convert a PDA using either convention into an equivalent PDA using the other.

Formal definition

Using the convention in the original lecture, a nondeterministic PDA is a six-tuple

\[ P=(Q,\Sigma,\Gamma,\delta,q_0,F), \]

where:

$Q$ is a finite set of states;
$\Sigma$ is the input alphabet;
$\Gamma$ is the stack alphabet;
$\delta$ is the transition function;
$q_0\in Q$ is the start state; and
$F\subseteq Q$ is the set of accepting states.

Let

\[ \Sigma_\varepsilon=\Sigma\cup\{\varepsilon\}, \qquad \Gamma_\varepsilon=\Gamma\cup\{\varepsilon\}. \]

Then

\[ \delta: Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon \rightarrow \mathcal{P}(Q\times\Gamma_\varepsilon). \]

Because the output is a set, the machine may have multiple possible moves.

Note

Many textbooks define a PDA as a seven-tuple $(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, where $Z_0$ is an explicit initial stack symbol. The lecture’s convention instead begins with an empty stack and pushes a bottom marker such as $ in an initial transition. The models are equivalent.

Reading a transition

A transition depends on three inputs:

the current state;
an input symbol—or $\varepsilon$ if no input is consumed; and
a stack symbol to pop—or $\varepsilon$ if nothing is popped.

It produces:

a new state; and
a stack symbol to push—or $\varepsilon$ if nothing is pushed.

For example,

\[ (q_2,A)\in\delta(q_1,a,\varepsilon) \]

means:

in state $q_1$;
consume a from the input;
pop nothing;
move to $q_2$; and
push $A$ onto the stack.

The corresponding edge label may be written

a, ε → A

If no transition applies to the current state, next input symbol, and stack top, that computation branch crashes and rejects.

Recognizing $\{a^nb^n:n\ge0\}$

The PDA uses the stack to remember how many as have appeared.

Push one marker + for each a.
When the first b arrives, enter a second state.
Pop one + for each b.
Accept only when the input has ended and every marker has been removed.

A PDA for matching a block of `a`s with an equally long block of `b`s.

Using $ as a bottom-of-stack marker, the essential transitions are:

\[ \delta(q_0,\varepsilon,\varepsilon)\ni(q_1,\$), \]

\[ \delta(q_1,a,\varepsilon)\ni(q_1,+), \]

\[ \delta(q_1,b,+)\ni(q_2,\varepsilon), \]

\[ \delta(q_2,b,+)\ni(q_2,\varepsilon), \]

\[ \delta(q_2,\varepsilon,\$)\ni(q_3,\varepsilon). \]

State $q_3$ is accepting. The empty string may be handled by making $q_0$ accepting or by adding an appropriate empty-input path.

Why malformed strings fail

A leading b has no + to pop.
An a after the machine enters the b phase has no transition.
Too many bs exhaust the markers too soon.
Too few bs leave markers on the stack when the input ends.

The stack provides precisely the unbounded counter-like memory a DFA lacks.

Recognizing $\{w\#w^R\}$

The separator # tells the machine exactly where the first half ends.

Use three phases:

$q_1$: before #, push each input symbol;
$q_2$: after #, match each symbol against the stack top and pop it; and
$q_3$: accept after the input ends and the bottom marker is reached.

For alphabet $\{a,b\}$, the transitions include:

\[ \delta(q_0,\varepsilon,\varepsilon)\ni(q_1,\$), \]

\[ \delta(q_1,a,\varepsilon)\ni(q_1,a), \qquad \delta(q_1,b,\varepsilon)\ni(q_1,b), \]

\[ \delta(q_1,\#,\varepsilon)\ni(q_2,\varepsilon), \]

\[ \delta(q_2,a,a)\ni(q_2,\varepsilon), \qquad \delta(q_2,b,b)\ni(q_2,\varepsilon), \]

\[ \delta(q_2,\varepsilon,\$)\ni(q_3,\varepsilon). \]

There is deliberately no transition for a mismatch such as reading a while b is on top. That branch crashes.

The transition specification for a PDA recognizing $w\#w^R$.

Balanced braces

A PDA can recognize balanced braces deterministically:

push { when reading an opening brace;
pop { when reading a closing brace;
reject if a closing brace appears without a matching opening brace; and
accept only if the input ends with no unmatched opening braces.

The stack stores the set of currently unmatched opening braces. Nesting depth may grow without bound, but only the most recently opened brace must be matched next.

A PDA specification for balanced braces.

Care is required when mixing $\varepsilon$-moves with deterministic behavior. If both an input-consuming transition and an $\varepsilon$-transition are available for the same state and stack top, the machine is nondeterministic.

Why palindromes require guessing

For

\[ \{w\#w^R:w\in\Sigma^*\}, \]

the separator tells the PDA when to switch from pushing to popping.

For an unmarked even-length palindrome

\[ \{ww^R:w\in\Sigma^*\}, \]

the midpoint is not marked. The PDA must guess when the first half ends:

push symbols while reading a possible first half;
nondeterministically switch to a matching state without consuming input;
match the remaining symbols against the stack; and
accept when the input and stored first half end together.

A nondeterministic PDA for even-length palindromes.

For palindromes of either parity, the machine needs three possible choices near the midpoint:

the next symbol begins the second half of an even-length palindrome;
the current symbol still belongs to the first half; or
the current symbol is the unpaired middle of an odd-length palindrome.

A PDA can nondeterministically choose among even and odd midpoint possibilities.

Nondeterminism lets the PDA explore every possible midpoint. The input is accepted if one guess produces a complete match.

Equal or unequal symbol counts

The language of strings containing equal numbers of as and bs is context-free even when the symbols may appear in any order.

One stack strategy stores the current unmatched excess:

when reading a, cancel a stored b if possible; otherwise push a;
when reading b, cancel a stored a if possible; otherwise push b; and
accept when the input ends with no unmatched symbols.

The stack holds only one kind of unmatched symbol at a time. Its height represents the absolute difference between the counts.

For strings with more as than bs, a related construction must accept exactly when at least one unmatched a remains after the input. This can be implemented deterministically by using the state to record which kind of symbol currently occupies the stack and carefully handling transitions when the final marker of one kind is canceled.

Deterministic and nondeterministic PDAs

Nondeterminism did not increase the expressive power of finite automata:

\[ \mathrm{DFA}=\mathrm{NFA}. \]

For pushdown automata, the situation is different. Nondeterministic PDAs recognize all context-free languages, while deterministic PDAs recognize the smaller class of deterministic context-free languages.

For example:

$\{w\#w^R\}$ is deterministic because # identifies the midpoint;
unmarked palindromes require nondeterministically guessing the midpoint; and
many programming-language grammars are intentionally designed to allow deterministic parsing.

Thus, nondeterminism genuinely increases the recognition power of PDAs.

From a CFG to a PDA

Theorem. Every context-free language is recognized by some nondeterministic PDA.

Given a CFG

\[ G=(V,\Sigma,R,S), \]

construct a PDA that simulates a derivation on its stack.

Invariant

At every stage, the stack contains the portion of a possible derived string that the machine still expects to match. The PDA nondeterministically chooses productions and checks terminal symbols against the actual input.

Construction

Use three states:

$q_0$ initializes the stack;
$q_1$ performs the simulation; and
$q_2$ accepts.

With $ as the bottom marker:

Push the start variable above $:

\[ \delta(q_0,\varepsilon,\varepsilon)\ni(q_1,S\$). \]
For every grammar production $A\rightarrow\alpha$, add an $\varepsilon$-transition that replaces $A$ on the stack by $\alpha$:

\[ \delta(q_1,\varepsilon,A)\ni(q_1,\alpha). \]
For each terminal $a\in\Sigma$, match it against the input and pop it:

\[ \delta(q_1,a,a)\ni(q_1,\varepsilon). \]
When only the bottom marker remains and the input is exhausted, enter the accepting state:

\[ \delta(q_1,\varepsilon,\$)\ni(q_2,\varepsilon). \]

If the implementation treats the left end of the pushed string as the stack top, it may need to push the right-hand side in reverse order. This is a representation detail, not a change to the construction’s logic.

The standard three-state construction converting a CFG into a PDA.

CFG-to-PDA example

Consider

\[ S\rightarrow aSc\mid T, \]

\[ T\rightarrow\varepsilon\mid aTb. \]

The grammar generates

\[ L(G)=\{a^{i+j}b^jc^i:i,j\ge0\}. \]

The PDA includes one expansion transition for each production:

\[ \delta(q_1,\varepsilon,S) \ni (q_1,aSc), (q_1,T), \]

\[ \delta(q_1,\varepsilon,T) \ni (q_1,\varepsilon), (q_1,aTb). \]

It also includes terminal-matching transitions:

\[ \delta(q_1,a,a)\ni(q_1,\varepsilon), \]

\[ \delta(q_1,b,b)\ni(q_1,\varepsilon), \]

\[ \delta(q_1,c,c)\ni(q_1,\varepsilon). \]

For input aabc, one successful branch chooses

\[ S\Rightarrow aSc\Rightarrow aTc\Rightarrow aaTbc\Rightarrow aabc. \]

The PDA makes the same nondeterministic production choices on its stack and then consumes matching terminals.

Grammar productions encoded as PDA stack-replacement transitions.

Why the construction works

The proof shows

\[ L(G)=L(P). \]

Both inclusions are required:

If $G$ derives $w$, the PDA can choose the corresponding production transitions and then match every terminal, so $w\in L(P)$.
If the PDA accepts $w$, its stack-replacement choices correspond to grammar productions, yielding a derivation of $w$, so $w\in L(G)$.

Nondeterminism is essential because the PDA must choose among all productions for the variable currently on top of the stack.

From a PDA to a CFG

The reverse construction is more technical but is also possible:

For every PDA $P$, there is a CFG $G$ such that $L(G)=L(P)$.

The standard proof first normalizes the PDA and then creates variables representing computations that move between pairs of states while removing designated stack symbols. Grammar productions compose these smaller computations.

Together, the two constructions establish

\[ \mathcal{L}(\mathrm{CFG}) = \mathcal{L}(\mathrm{PDA}) = \mathrm{CFL}. \]

CFGs and nondeterministic PDAs are therefore equally powerful descriptions of the context-free languages.

Every regular language is context-free

A DFA can be viewed as a PDA that never changes or inspects its stack. Therefore every regular language is context-free:

\[ \mathrm{REG}\subseteq\mathrm{CFL}. \]

The inclusion is proper because a PDA can recognize languages such as $\{a^nb^n:n\ge0\}$, which no finite automaton can recognize.

CFGs and PDAs are equivalent in power; a DFA is a PDA whose stack is unused.

Check your understanding

What information can a stack retain that a DFA state cannot?
What do the three inputs to a PDA transition represent?
Why does $\{w\#w^R\}$ not require guessing the midpoint?
Why do unmarked palindromes require nondeterminism?
How does the CFG-to-PDA construction simulate a derivation?
Why does the proof of CFG–PDA equivalence require both inclusions?
Why are nondeterministic PDAs more powerful than deterministic PDAs even though NFAs and DFAs are equivalent?