Pushdown Automata

A pushdown automaton (PDA) is an NFA equipped with a stack. The stack provides unbounded memory that is accessible only at the top, which is exactly the power needed for context-free languages: every CFG has an equivalent PDA and every PDA has an equivalent CFG. The working skills are designing PDAs for matching languages such as $\{a^n b^n\}$, acceptance by empty stack versus final state, and the CFG $\Leftrightarrow$ PDA equivalence at a constructive level.

A PDA is $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ where $\Gamma$ is the stack alphabet, $Z_0 \in \Gamma$ is the start stack symbol, and

A transition $\delta(q, a, X) \ni (p, \gamma)$ means: in state $q$, reading $a$ (or $\varepsilon$), with $X$ on top of the stack, pop $X$, push the string $\gamma$ (rightmost symbol ends on top), and go to $p$.

A configuration (ID) is $(q, w, \alpha)$ with state $q$, unread input $w$, and stack string $\alpha$ (left = bottom, right = top, or the opposite convention; state the convention). These notes write the top at the right end of $\alpha$.

A stack holding only $Z_0$ is not empty. A machine that ends with $Z_0$ left accepts only if it is in a final state and the question uses final-state acceptance.

For nondeterministic PDAs the two modes are equivalent: every final-state PDA can be converted into an empty-stack PDA for the same language and back (Example 3). CFLs are exactly the languages of nondeterministic PDAs in either mode. For deterministic PDAs they are not equivalent: empty-stack DPDAs accept only languages with the prefix property, a proper subset of the final-state DPDA languages.

If $\delta$ never has a choice (including no competing $\varepsilon$-move when a symbol move exists), the PDA is deterministic. DPDAs define a proper subclass of CFLs (next note).

Informal design: on each $a$, push $A$; on each $b$, pop $A$; when only the bottom marker $Z$ is left, pop it with an $\varepsilon$-move, leaving the stack empty, and accept by empty stack. A run dies if a $b$ finds $Z$ instead of $A$ or if an $a$ follows a $b$; if $A$'s remain, $Z$ is never exposed and the stack never empties.

Two precise versions. Stack top at the right, and $Z$ is the bottom marker $Z_0$; a transition is written $q \xrightarrow{a,\;X \to \gamma} p$ (read $a$ or $\varepsilon$, replace top $X$ by $\gamma$).

In short, the empty-stack machine uses a,Z/ZA; a,A/AA; b,A/$\varepsilon$; $\varepsilon$,Z/$\varepsilon$, with state $q_1$ recording "a $b$ has been read" so that no $a$ is accepted after it. The run in the figure, written as IDs $(q, \text{unread input}, \text{stack})$: $(q_0, aabb, Z) \vdash (q_0, abb, ZA) \vdash (q_0, bb, ZAA) \vdash (q_1, b, ZA) \vdash (q_1, \varepsilon, Z) \vdash (q_1, \varepsilon, \varepsilon)$. The last move pops $Z$; the input is used up and the stack is empty, so aabb is accepted. The final-state version instead ends with $(q_f, \varepsilon, Z)$ and accepts because $q_f \in F$, with $Z$ still on the stack; its start state is final, so $\varepsilon$ is accepted without a move.

Determinism. The empty-stack version is not deterministic: in $q_0$ with $Z$ on top it may pop $Z$ (to accept $\varepsilon$) or read $a$. The final-state version is deterministic: no state has an $\varepsilon$-move and a symbol move on the same top symbol. This is unavoidable. A DPDA accepting by empty stack halts with an empty stack after any accepted string, so it cannot then accept a longer one; since $\varepsilon$ and ab are both in $\{a^n b^n\}$, no DPDA accepts this language by empty stack, although one accepts it by final state.

Traces of rejected strings (final-state version): aabbab reaches $q_2$ and then reads a, for which $q_2$ has no move; aaabb ends in $q_2$ with $ZA$ on the stack, so the finishing move does not apply; abab fails like aabbab.

Standard construction: start by pushing $S$; while top is a variable $A$, replace it by the reversed RHS $\alpha^R$, so $\delta(q,\varepsilon,A)$ contains $(q,\alpha^R)$ (nondeterministic choice of production); while top is a terminal $a$, read $a$ from input and pop. Accept by empty stack. This PDA may use $\varepsilon$-moves heavily, and it needs only one state: every CFL is accepted by empty stack by a single-state PDA. Read from top to bottom, the stack holds the unexpanded part of a leftmost sentential form, so the run simulates a leftmost derivation.

For $S \to aSb \mid \varepsilon$ (top written first in this paragraph, to read like the sentential form): on ab the stack goes $S \to aSb$ (expand), read a leaving $Sb$, expand $S \to \varepsilon$ leaving $b$, read b, stack empty: accept. A wrong guess (expanding $S \to aSb$ a second time) simply dies.

More technical: variables remember triples $[p,X,q]$ meaning "pop $X$ going from $p$ to $q$". The full construction is long; know that it exists and that the grammar has $|Q|^2 |\Gamma|$ variables $[p,X,q]$, plus the start symbol.

FIFO extraction is fair for this finitely branching transition system: each enqueued configuration is eventually processed. Exact duplicate configurations are suppressed by seen. Arbitrary epsilon-looping PDAs can generate infinitely many distinct stacks, so this search need not terminate on rejection.

One successful run proves acceptance; one failed run does not prove rejection. Rejection requires ruling out every branch or using a complete membership algorithm (for example, via a CFG).

Parse trees expand the leftmost variable; the PDA stack stores the fringe of unfinished siblings. That is why one stack equals one "context-free" matching discipline, not $\{a^n b^n c^n\}$.

$L$ is context-free iff some PDA accepts $L$ by empty stack iff some PDA accepts $L$ by final state.

Run of the empty-stack PDA on aaabbb: push three $A$'s, pop three, leaving $Z$; the $\varepsilon$-move pops $Z$ and the empty stack accepts. On aabbb: after two pushes and two pops, $Z$ is on top with one $b$ unread; no move reads $b$ on $Z$, and popping $Z$ leaves input unread, so every run fails. On aab: one $A$ remains above $Z$ when the input ends, the stack cannot empty, reject.

Nondeterministically guess the middle: push while reading the first half, then pop matching symbols while reading the reverse half. Deterministic PDAs cannot find the middle of even-length palindromes over a 2-letter alphabet in general.

Convert empty-stack PDA to final-state: add a bottom marker, and when original stack would empty, move to a new accept state. Conversely, push a new bottom, simulate, and on original accept drain the stack with $\varepsilon$-pops.

Nondeterministically choose which equality to check; push on the first letter run, pop on the second. Cannot check both equalities at once with one stack.

The surplus PDA on abba: push $A$ (stack $ZA$), pop on $b$ ($Z$), push $B$ on $b$ ($ZB$), pop on $a$ ($Z$): accept. On aab the stack ends as $ZA$: reject.

So $\{a^n b^n c^n\}$ needs either more structure than one stack (a linear-bounded automaton suffices) or a second stack.

Common misconceptions.