Pushdown Automata (PDA)

CS305 -- Formal Language Theory

Use ← → arrows to navigate · 24 slides

The Big Picture: PDA = NFA + Stack

A Pushdown Automaton extends an NFA with a stack -- an infinite, last-in-first-out memory.

DFA/NFA -- regular languages
PDA -- context-free languages
Turing Machine -- recursively enumerable

Key Idea

The stack lets the PDA "remember" unbounded information in LIFO order. This is exactly the power needed to match nested structures like aⁿbⁿ and balanced parentheses.

Why Do We Need a Stack?

A DFA has finite memory (just its state). It cannot count beyond a fixed bound.

Consider L = { aⁿbⁿ | n ≥ 0 }:

A DFA needs a separate state per count of a's
But n can be any number -- infinitely many states
The Pumping Lemma proves no DFA suffices

Solution: Add a stack! Push each a, pop one per b. Accept if stack is empty.

Analogy: Cafeteria Tray Stack

A spring-loaded tray dispenser. You only see the top tray. Push on, pop off. Never reach into the middle.

DFA vs PDA Race

Click a test case above

The PDA Machine Model

A PDA has three components: an input tape, a finite control (state), and a stack (unbounded LIFO).

Press Step or Run (input: aabb)

At each step: 1. Read input symbol (or ε) 2. Peek at stack top 3. Based on (state, input, stack_top), transition to new state and modify stack

Formal Definition of a PDA

A PDA is a 7-tuple:

M = (Q, Σ, Γ, δ, q₀, Z₀, F)

The Transition Function

δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)

Key Idea

The range is a set of (state, string) pairs -- PDAs are nondeterministic. The PDA "chooses" among moves. Accepts if any choice leads to acceptance.

Watch Out

Σ is the input alphabet (e.g. {a,b}). Γ is the stack alphabet (e.g. {a,b,$}). They can overlap, but Γ often has extra symbols like bottom marker $.

Reading PDA Transitions

Each transition:

δ(q, a, X) contains (p, Y)

Read as: "In state q, reading a, with X on top, move to p and replace X with Y."

Key Idea

String Y is pushed so its leftmost symbol ends on top. If Y = ABC, then A is on top.

Transition Explorer

Select a transition above

Push, Pop, and No-Change Operations

Every transition pops the stack top and pushes a replacement. We encode push, pop, and no-change via this single mechanism.

PUSH (add B on top of X)

δ(q, a, X) = {(p, BX)}

Pop X, push BX. Net: B appears on top, X stays below.

POP (remove X)

δ(q, a, X) = {(p, ε)}

Pop X, push nothing. X is gone.

NO-CHANGE

δ(q, a, X) = {(p, X)}

Pop X, push X back. Stack unchanged.

MULTI-PUSH

δ(q, a, X) = {(p, ABC)}

Pop X, push ABC. A on top (leftmost = top).

Example: PDA for { aⁿbⁿ | n ≥ 0 }

Strategy

Start with $ on the stack
For each a: push a
Switch to "b-reading" mode
For each b: pop one a
Accept if stack has only $

Key Idea

The stack counts a's. Each b cancels one a. If counts match, stack returns to $.

Transitions

δ(q0, a, $) = {(q0, a$)}
δ(q0, a, a) = {(q0, aa)}
δ(q0, ε, $) = {(qacc, $)}
δ(q0, b, a) = {(q1, ε)}
δ(q1, b, a) = {(q1, ε)}
δ(q1, ε, $) = {(qacc, $)}

Interactive Simulator

Acceptance: Final State vs. Empty Stack

There are two equivalent ways a PDA can accept a string.

1. Acceptance by Final State

Accept if ALL input consumed and PDA is in state q ∈ F. Stack contents do not matter.

2. Acceptance by Empty Stack

Accept if ALL input consumed and stack is completely EMPTY. Current state does not matter.

Key Idea

These two modes are equivalent in power. Any language accepted by final state can also be accepted by empty stack (via a different PDA), and vice versa. We can mechanically convert between them.

Converting Between Acceptance Modes

Final State → Empty Stack

1. Add new start q0', push new bottom marker Z0' under Z0. 2. From every final state, ε-transition to q_drain. 3. q_drain pops everything.

Empty Stack → Final State

1. Add new start q0', push Z0' under Z0. 2. From EVERY state, ε-transition to q_f when Z0' is on top. 3. q_f is only accept state.

Watch Out

The new bottom marker Z0' is essential! Without it, the original PDA might empty its stack prematurely and the conversion would accept strings it should not.

Example: Balanced Parentheses PDA

Language: { w ∈ {(, )}* | w has properly nested, balanced parentheses }

Strategy

Push marker L for each (
Pop marker L for each )
Accept if stack returns to just $

Transitions

δ(q0, (, $) = {(q0, L$)}
δ(q0, (, L) = {(q0, LL)}
δ(q0, ), L) = {(q0, ε)}
δ(q0, ε, $) = {(qacc, $)}

Watch Out

Seeing ) when stack has only $ means unmatched close paren -- machine gets stuck (reject).

Interactive Simulator

Challenge: Predict the PDA State

Challenge A

Consider the aⁿbⁿ PDA from Slide 8. After processing the input aaab (3 a's then 1 b), what is the current configuration?

Example: PDA for { ww^R | w ∈ {0,1}* }

Even-length palindromes! The second half is the reverse of the first.

The Problem

0110: first half 01, second half 10 = reverse of 01.

But how does the PDA know where the middle is?

Key Idea: Nondeterminism!

The PDA guesses the midpoint! At every position it branches:

"Haven't reached middle" -- keep pushing
"This IS the middle!" -- switch to popping

Accepts if any guess leads to acceptance.

Analogy

Clone yourself at every step. One clone keeps pushing, the other switches to matching. Most clones die. The one who guessed right survives.

Palindrome Simulator

DPDA vs NPDA: Nondeterminism Matters!

Recall: DFA vs NFA

For finite automata: deterministic = nondeterministic in power.

DFA = NFA (same languages: regular)

For PDAs: NOT the same!

DPDA < PDA (strict subset!)

What is a DPDA?

A deterministic PDA has at most one move per configuration. No branching, no guessing.

Critical Difference

{ ww^R } is context-free but NOT deterministic context-free. The "guess the middle" trick requires nondeterminism.

Key Idea

Deterministic CFLs matter in practice: most programming languages are DCFLs so parsers run efficiently.

Language	DPDA?	PDA?
aⁿbⁿ	Yes	Yes
ww^R	No	Yes
wcw^R	Yes	Yes

Challenge: Fix the Bug in This PDA

Challenge B

This PDA is supposed to accept { aⁿbⁿ | n ≥ 1 } but has a bug. Which transition is wrong?

δ(q0, a, $) = {(q0, a$)}
δ(q0, a, a) = {(q0, aa)}
δ(q0, b, a) = {(q1, ε)}
δ(q1, b, a) = {(q1, ε)}
δ(q1, ε, $) = {(q1, $)} ← Transition 5

What is wrong with Transition 5?

CFG to PDA Conversion

Given any CFG G, we build a PDA M with L(M) = L(G). Uses top-down parsing.

The Construction (3 states!)

Key Idea

The stack holds a "prediction" of remaining input. Variables get expanded (replaced by rule RHS). Terminals get matched and consumed. This simulates a leftmost derivation.

Step-Through: Parsing "aabb"

Grammar: S → aSb | ε (generates aⁿbⁿ)

0 / 9

PDA to CFG Conversion

Every PDA can be converted to an equivalent CFG — the reverse direction of the equivalence.

High-Level Idea

For each pair of states (p, q), create a variable A_pq that generates all strings taking the PDA from state p with empty stack to state q with empty stack.

Key Idea

The grammar variable A_pq represents "what the PDA does between states p and q." This captures every possible computation path.

Warning

This conversion can produce exponentially many rules! The resulting CFG is correct but usually not practical — it's a theoretical tool.

The Big Equivalence: PDA = CFG

This is one of the most important results in formal language theory.

Theorem

A language is context-free if and only if some PDA recognizes it.

CFL = {L | some CFG generates L} = {L | some PDA recognizes L}

Analogy

Like how DFAs, NFAs, and regex are three equivalent ways to describe regular languages, CFGs and PDAs are two equivalent ways to describe context-free languages.

This means: any language you can describe with recursive production rules, you can also recognize with a stack-based machine, and vice versa.

Limitations: What PDAs Cannot Do

The stack gives power beyond DFAs, but it's still limited.

Cannot recognize:

{aⁿbⁿcⁿ} — needs to match THREE counts
{ww} — needs to compare non-nested halves
{aⁿb^mcⁿd^m} — cross-serial dependencies

Why?

A stack is LIFO — you can only match in nested (palindromic) patterns. Matching in crossing patterns requires more memory (like a Turing machine tape).

Key Insight

DPDA ⊊ NPDA: Unlike DFA=NFA, deterministic PDAs are strictly weaker than nondeterministic ones! {ww^R} needs nondeterminism to guess the middle.

Challenge C: What Can a PDA Recognize?

Classify each language

For each language, decide: PDA can recognize, or PDA cannot?

1. {aⁿb²ⁿ | n ≥ 0}

2. {aⁿbⁿcⁿ | n ≥ 0}

3. {ww^R | w ∈ {0,1}*}

4. {ww | w ∈ {0,1}*}

Summary & Cheat Sheet

Concept	Key Point
PDA	NFA + Stack = CFL recognizer
7-tuple	(Q, Σ, Γ, δ, q₀, Z₀, F)
Transitions	δ(q, a, X) = {(p, Y)}
Acceptance	Final state or empty stack
Equivalence	PDA ≡ CFG (both define CFLs)
DPDA ⊊ NPDA	Nondeterminism adds power!
Limits	Can't do aⁿbⁿcⁿ or ww

Quiz: Multiple Choice

Q1: What does a PDA add to an NFA?

A second tape A stack (LIFO memory) A queue (FIFO memory)

Q2: Which language can a PDA recognize?

{aⁿbⁿcⁿ} {aⁿbⁿ} {ww}

Q3: Are DPDA and NPDA equivalent?

Yes, just like DFA=NFA No, NPDA is strictly more powerful No, DPDA is more powerful

Quiz: Trace the PDA

Complete the computation

PDA for {aⁿbⁿ}: start in q0 with stack [$]. Input: aabbb

Fill in the missing stack contents and final result:

Step 0: (q0, aabbb, $)

Step 1: Read a, push a: (q0, abbb, )

Step 2: Read a, push a: (q0, bbb, )

Step 3: Read b, pop a: (q1, bb, a$)

Step 4: Read b, pop a: (q1, b, $)

Step 5: Read b, stack top is $:

Quiz: Design a PDA

Build transitions for {0ⁿ1ⁿ | n ≥ 1}

Fill in the missing parts of these PDA transitions:

1. δ(q0, 0, $) = {(q0, )}

First 0: push onto empty stack

2. δ(q0, 0, 0) = {(q0, )}

More 0's: keep pushing

3. δ(q0, 1, 0) = {(, ε)}

Switch to reading 1's

4. δ(q1, ε, $) = {(q_acc, $)}

Accept when stack empty

Pushdown Automata (PDA)

The Big Picture: PDA = NFA + Stack

Key Idea

Why Do We Need a Stack?

Analogy: Cafeteria Tray Stack

DFA vs PDA Race

The PDA Machine Model

Formal Definition of a PDA

The Transition Function

Key Idea

Watch Out

Reading PDA Transitions

Key Idea

Transition Explorer

Push, Pop, and No-Change Operations

PUSH (add B on top of X)

POP (remove X)

NO-CHANGE

MULTI-PUSH

Example: PDA for { anbn | n ≥ 0 }

Strategy

Key Idea

Transitions

Interactive Simulator

Acceptance: Final State vs. Empty Stack

1. Acceptance by Final State

2. Acceptance by Empty Stack

Key Idea

Converting Between Acceptance Modes

Final State → Empty Stack

Empty Stack → Final State

Watch Out

Example: Balanced Parentheses PDA

Strategy

Transitions

Watch Out

Interactive Simulator

Challenge: Predict the PDA State

Challenge A

Example: PDA for { wwR | w ∈ {0,1}* }

The Problem

Key Idea: Nondeterminism!

Analogy

Palindrome Simulator

DPDA vs NPDA: Nondeterminism Matters!

Recall: DFA vs NFA

For PDAs: NOT the same!

What is a DPDA?

Critical Difference

Key Idea

Challenge: Fix the Bug in This PDA

Challenge B

CFG to PDA Conversion

The Construction (3 states!)

Key Idea

Step-Through: Parsing "aabb"

PDA to CFG Conversion

High-Level Idea

Key Idea

Warning

The Big Equivalence: PDA = CFG

Theorem

Analogy

Limitations: What PDAs Cannot Do

Cannot recognize:

Why?

Key Insight

Challenge C: What Can a PDA Recognize?

Classify each language

Summary & Cheat Sheet

Quiz: Multiple Choice

Quiz: Trace the PDA

Complete the computation

Quiz: Design a PDA

Build transitions for {0n1n | n ≥ 1}

Example: PDA for { aⁿbⁿ | n ≥ 0 }

Example: PDA for { ww^R | w ∈ {0,1}* }

Build transitions for {0ⁿ1ⁿ | n ≥ 1}