Pushdown automata

Why it exists

A finite automaton has only a finite memory, so it cannot match $a^n b^n$. Add an unbounded stack and the machine can count: push one symbol for every $a$, pop one for every $b$. The resulting machine, the pushdown automaton (PDA), is exactly as powerful as a context-free grammar (next page). GATE asks: design a PDA, say which language a given PDA accepts, trace a computation, count stack operations, decide which languages a PDA can accept.

Prerequisites

A PDA is an NFA plus a stack (NFA; the stack operations are as in the stack ADT).

Precise definitions

A pushdown automaton is a 7-tuple $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$:

• $Q$ finite set of states, $\Sigma$ input alphabet, $\Gamma$ stack alphabet;
• $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to$ finite subsets of $Q \times \Gamma^*$ (the transition function);
• $q_0$ start state, $Z_0 \in \Gamma$ initial stack symbol (the bottom marker), $F \subseteq Q$ accepting states.

A move: if $(p, \gamma) \in \delta(q, a, X)$ then in state $q$ with input symbol $a$ next (or none read if $a = \varepsilon$) and $X$ on top of the stack, the machine pops $X$, pushes the string $\gamma$ (written so that its first symbol ends up on top) and enters state $p$. Every move pops exactly one symbol and pushes zero or more.

An instantaneous description (configuration) is $(q, w, \alpha)$: current state, unread input, stack contents (top first). $(q, aw, X\beta) \vdash (p, w, \gamma\beta)$ if $(p, \gamma) \in \delta(q, a, X)$; with $\varepsilon$ in place of $a$ the input is unchanged.

Two standard acceptance conditions:

• by final state: $L(P) = \{w : (q_0, w, Z_0) \vdash^* (q, \varepsilon, \alpha) \text{ for some } q \in F, \alpha \in \Gamma^*\}$ (the stack is ignored);
• by empty stack: $N(P) = \{w : (q_0, w, Z_0) \vdash^* (q, \varepsilon, \varepsilon)\}$ (the final states are ignored).

Theorem. The two conditions define the same class of languages: from a PDA accepting by final state one builds one accepting by empty stack with the same language, and conversely (constructions below; checked on named and random PDAs).

A PDA is deterministic (DPDA) if for every state, input symbol and stack top at most one move applies, counting $\varepsilon$-moves: if $\delta(q, \varepsilon, X)$ is non-empty then $\delta(q, a, X)$ is empty for every $a$. Otherwise it is nondeterministic; a string is accepted if some computation accepts.

How it works

Reading a computation

The first machine accepts $a^n b^n$ ($n \ge 0$) and is deterministic. States $q_0$ (start, accepting: the empty string), $q_1$ (reading $a$'s), $q_2$ (reading $b$'s), $q_3$ (accepting). Moves:

• $\delta(q_0, a, Z) = \{(q_1, AZ)\}$: first $a$: push $A$ above the bottom marker;
• $\delta(q_1, a, A) = \{(q_1, AA)\}$: every further $a$ pushes another $A$;
• $\delta(q_1, b, A) = \{(q_2, \varepsilon)\}$ and $\delta(q_2, b, A) = \{(q_2, \varepsilon)\}$: every $b$ pops an $A$;
• $\delta(q_2, \varepsilon, Z) = \{(q_3, Z)\}$: when only the marker is left, accept.

Computation on $aaabbb$ (the stack is shown with its top at the left; the table is the transition function, the outlined cell is the move used):

The stack grows to $n + 1$ symbols (the $n$ markers $A$ and $Z$) and the machine accepts when the stack is back to $Z$ with all input read. It rejects $aab$ (it ends with an $A$ left, no move to $q_3$), $aabbb$ (the third $b$ finds $Z$ on top and no move) and $ba$ (no move from $q_0$ on $b$).

Nondeterminism: even palindromes

A PDA cannot know where the middle of $w w^R$ is. It guesses: while reading the first half it pushes each symbol; at some moment it takes an $\varepsilon$-move into the second half, where it pops a symbol for every matching input symbol.

• $\delta(q_0, c, Z) = \{(q_0, cZ)\}$ and $\delta(q_0, c, t) = \{(q_0, ct)\}$ for $c, t \in \{a, b\}$: push the symbol read;
• $\delta(q_0, \varepsilon, X) = \{(q_1, X)\}$ for $X \in \{a, b, Z\}$: guess the middle;
• $\delta(q_1, c, c) = \{(q_1, \varepsilon)\}$: match and pop; $\delta(q_1, \varepsilon, Z) = \{(q_2, Z)\}$, $q_2$ accepting.

On $abba$ one computation accepts (guessing the middle after $ab$):

All computations are followed at once in the table of configurations. After the whole input there are $4$ of them; one is in the accepting state $q_2$ with the stack $Z$:

This machine is nondeterministic ($\delta(q_0, \varepsilon, X)$ and $\delta(q_0, c, X)$ both apply). That is not an accident: no DPDA accepts the set of even palindromes (textbook theorem, proved on the next batch's page).

More machines (each verified on all strings up to a length bound)

• Equal numbers of $a$ and $b$ (any order): one state; the stack holds the surplus. On $a$: pop a $B$ if one is on top (cancel), otherwise push $A$; on $b$: pop an $A$ if one is on top, otherwise push $B$. Accept when only $Z$ is left (and the input is used up).
• Balanced parentheses: push a marker on $($, pop on $)$; accept with only $Z$ left.
• $a^i b^j c^k$ with $i = j$ or $j = k$: at the start guess which of the two comparisons to make (an $\varepsilon$-move into one of two branches): branch one pushes for $a$, pops for $b$, ignores $c$; branch two ignores $a$, pushes for $b$, pops for $c$.

From final state to empty stack, and back

• Final state $\to$ empty stack. Put a new bottom marker $X_0$ under $Z_0$ and a new start state that pushes $Z_0$ above it. From every accepting state add an $\varepsilon$-move to a new state $p_e$ that pops everything (including $X_0$). The new marker stops the machine from emptying its stack by accident.
• Empty stack $\to$ final state. Add a new marker $X_0$ under $Z_0$; whenever $X_0$ becomes the top (the old stack is empty), move to a new accepting state.

What a PDA cannot do

One stack gives one unbounded counter that can be compared once. $\{a^n b^n c^n\}$ and $\{ww\}$ (no reversal) are not accepted by any PDA (the pumping lemma for CFLs, later; quoted here). A PDA with two stacks is as powerful as a Turing machine (textbook theorem, quoted). A PDA that does not use its stack is just an NFA, so every regular language is accepted by a PDA.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The machines of this page are the machines of the next one: every grammar has a PDA and every PDA a grammar (PDA and CFG); the deterministic subclass matters for parsing (deterministic versus nondeterministic PDA); the NFA is a PDA that ignores its stack (NFA).

PYQs

Consider the pushdown automaton (PDA) P below,
which runs on the input alphabet {a, b}, has stack
alphabet {⊥, A}, and has three states {s, p, q}, with s
being the start state. A transition from state u to state v,
labelled c/X/γ, where c is an input symbol or , X is a
stack symbol, and γ is a string of stack symbols,
represents the fact that in state u, the PDA can read c
from the input, with X on the top of its stack, pop X from
the stack, push in the string γ on the stack, and go to state
v. In the initial configuration, the stack has only the
symbol ⊥ in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the
language accepted by P?

In a pushdown automaton P=(Q,Σ,Γ,δ,q0,F), a
transition of the form,

 where p, q∈Q, a ∈ Σ ∪ {ε}, X , Y ∈ Γ∪ {ε},
represents:(q,Y) ∈ δ(p,a,X)
Consider the following p ushdown automaton over the
input alphabet Σ={a,b} and stack alphabet Γ={#,A}.

 The number of strings of length 100 accepted by the above
pushdown automaton is ___________

Consider the transition diagram of a PDA given below
with input alphabet Σ = {a,b} and stack alphabet Γ =
{X,Z}. Z is the initial stack symbol. Let L denote the
language accepted by the PDA.

Which one of the following is TRUE?

Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ =
{0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual
convention) Q is the set of states, Σ is the input alphabet,
Γ is stack alphabet, δ is the state transition function, q0
is the initial state, ⊥ is the initial stack symbol, and F is
the set of accepting states, The state transition is as
follows:

 Which one of the following sequences must follow the
string 101100 so that the overall string is accepted by
the automaton?

Consider the pushdown automaton (PDA) below which
runs over the input alphabet (a,b,c). It has the stack
alphabet { Z0,X } where Z0 is the bottom-of-stack marker.
The set of states of the PDA is (s,t,u,f) where s is the start
state and f is the final state. The PDA accepts by final state.
The transitions of the PDA given below are depicted in a
standard manner. For example, the transition (s,b,X)-
(t,XZ0) means that if the PDA is in state s and the symbol
on the top of the stack is X, then it can read b from the
input and move to state t after popping the top of stack and
pushing the symbols Z0 and X (in that order) on the stack.
(s,a,Z0) → (s,XXZ0)
(s,∈,Z0) → (f,∈)
(s,a,X) → (s,XXX)
(s,b,X) → (t,∈)
(t,b,X) → (t,∈)
(t,c,X) → (u,∈)
(u,c,X) → (u,∈)
(u,∈,Z0) → (f,∈)
The Language accepeted by the PDA is

Let P be a non-deterministic push-down automaton
(NPDA) with exactly one state, q, and exactly one symbol
Z, in its stack alphabet. State q is both the starting as well
as the accepting state of the PDA. The stack is initialized
with one Z before the start of the operation of the PDA.
Let the input alphabet of the PDA be Σ. Let L(P) be the
language accepted by the PDA by reading a string and
reaching its accepting state. Let N{P} be the language
accepted by the PDA by reading a string and emptying its
stack. Which of the following statements is TRUE?

Self-check

Revision card

References