Push Down Automata

Exam Importance: Very High

PDA design questions appear in every paper (100% frequency). Common patterns: aⁿbⁿ, aⁿb²ⁿ, palindromes. This module typically carries 10 marks. Master the stack operations!

Introduction to Push Down Automata

What is a Push Down Automaton?

A Push Down Automaton (PDA) is a finite automaton enhanced with an auxiliary memory called a stack. This stack provides unlimited memory, making PDAs more powerful than FAs.

PDA = FA + Stack

Structure of a PDA: Input tape, Finite Control, and Stack

Stack Operations

Operation	Description	Notation
Push	Add symbol to top of stack	Replace X with YX (Y pushed on top)
Pop	Remove symbol from top of stack	Replace X with ε (X removed)
Replace	Change top symbol	Replace X with Y
No Change	Leave stack unchanged	Replace X with X

Formal Definition of PDA

7-Tuple Definition

A PDA is a 7-tuple: P = (Q, Σ, Γ, δ, q₀, Z₀, F) where:

Q = Finite set of states
Σ = Input alphabet
Γ = Stack alphabet
δ = Transition function: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
q₀ = Initial state (q₀ ∈ Q)
Z₀ = Initial stack symbol (Z₀ ∈ Γ)
F = Set of final/accepting states (F ⊆ Q)

Example

PDA for L = {aⁿbⁿ | n ≥ 1}

Tuple Definition:

Q = {q₀, q₁, q₂}
Σ = {a, b}
Γ = {X, Z₀}
q₀ = q₀ (start state)
Z₀ = Z₀ (initial stack symbol)
F = {q₂}

PDA Transitions

Transition Notation

A transition is written as:

Format: δ(q, a, X) = {(p, γ), ...}

Meaning: In state q, reading input a, with X on top of stack:

Move to state p
Replace X with γ on the stack

Transition Types

Transition	Stack Effect	Example
δ(q, a, X) = {(p, YX)}	Push Y (Y goes on top of X)	On 'a', push marker
δ(q, a, X) = {(p, ε)}	Pop X (X is removed)	On 'b', remove marker
δ(q, a, X) = {(p, Y)}	Replace X with Y	Change stack top
δ(q, ε, X) = {(p, γ)}	ε-transition (no input read)	Spontaneous move

Instantaneous Description (ID)

The configuration of a PDA at any moment is described by a triple:

(q, w, γ)

Where:

q = current state
w = remaining input
γ = stack contents (leftmost = top)

Acceptance Modes

A PDA can accept strings in two equivalent ways:

1. Acceptance by Final State

A string w is accepted if:

Starting from (q₀, w, Z₀)
The PDA can reach (qf, ε, γ) where qf ∈ F
The input is completely consumed
Stack contents don't matter

(q₀, w, Z₀) ⊢* (qf, ε, γ) where qf ∈ F

2. Acceptance by Empty Stack

A string w is accepted if:

Starting from (q₀, w, Z₀)
The PDA can reach (q, ε, ε)
Input consumed AND stack is empty
Current state doesn't matter

(q₀, w, Z₀) ⊢* (q, ε, ε)

Equivalence

Both acceptance modes are equivalent in power. Any language accepted by one mode can be accepted by the other (with a modified PDA).

PDA Design Patterns

Common Exam Patterns

Master these patterns - they cover 90% of PDA questions:

Counting: aⁿbⁿ, aⁿb²ⁿ
Palindromes: wcwᴿ, wwᴿ

Pattern 1: Equal Counting (aⁿbⁿ)

Complete Example

PDA for L = {aⁿbⁿ | n ≥ 1}

Strategy:

For each 'a', push X onto stack
For each 'b', pop one X from stack
Accept when input ends and stack has only Z₀

Transitions:

δ(q₀, a, Z₀) = {(q₀, XZ₀)}    -- First 'a': push X
δ(q₀, a, X)  = {(q₀, XX)}     -- More 'a's: push X
δ(q₀, b, X)  = {(q₁, ε)}      -- First 'b': pop X, change state
δ(q₁, b, X)  = {(q₁, ε)}      -- More 'b's: pop X
δ(q₁, ε, Z₀) = {(q₂, Z₀)}     -- End: accept if stack has Z₀
                            

Trace for "aabb":

Step	State	Remaining Input	Stack	Action
0	q₀	aabb	Z₀	Start
1	q₀	abb	XZ₀	Read 'a', push X
2	q₀	bb	XXZ₀	Read 'a', push X
3	q₁	b	XZ₀	Read 'b', pop X
4	q₁	ε	Z₀	Read 'b', pop X
5	q₂	ε	Z₀	ε-move to accept

Result: Accepted! (in state q₂ ∈ F)

Pattern 2: Double Counting (aⁿb²ⁿ)

Complete Example

PDA for L = {aⁿb²ⁿ | n ≥ 1}

Strategy:

For each 'a', push TWO X's onto stack
For each 'b', pop ONE X from stack
Accept when input ends and stack has only Z₀

Transitions:

δ(q₀, a, Z₀) = {(q₀, XXZ₀)}   -- First 'a': push XX
δ(q₀, a, X)  = {(q₀, XXX)}    -- More 'a's: push XX (net +2)
δ(q₀, b, X)  = {(q₁, ε)}      -- First 'b': pop X
δ(q₁, b, X)  = {(q₁, ε)}      -- More 'b's: pop X
δ(q₁, ε, Z₀) = {(q₂, Z₀)}     -- Accept
                            

Alternative (push once, pop half):

Push X for each 'a'. Pop X for every TWO 'b's using an intermediate state.

Pattern 3: Palindromes with Center Marker

Complete Example

PDA for L = {wcwᴿ | w ∈ {a,b}*}

Strategy:

Push all symbols before 'c' onto stack
When 'c' is seen, change state (don't push)
Match remaining input with stack (pop on match)
Accept if stack is empty when input ends

Transitions:

-- Phase 1: Push first half
δ(q₀, a, Z₀) = {(q₀, aZ₀)}
δ(q₀, b, Z₀) = {(q₀, bZ₀)}
δ(q₀, a, a)  = {(q₀, aa)}
δ(q₀, a, b)  = {(q₀, ab)}
δ(q₀, b, a)  = {(q₀, ba)}
δ(q₀, b, b)  = {(q₀, bb)}

-- Phase 2: See center marker
δ(q₀, c, a)  = {(q₁, a)}      -- c seen, don't change stack
δ(q₀, c, b)  = {(q₁, b)}
δ(q₀, c, Z₀) = {(q₁, Z₀)}     -- for wcwᴿ where w = ε

-- Phase 3: Match and pop
δ(q₁, a, a)  = {(q₁, ε)}      -- match a with a, pop
δ(q₁, b, b)  = {(q₁, ε)}      -- match b with b, pop

-- Accept
δ(q₁, ε, Z₀) = {(q₂, Z₀)}
                            

Trace for "abcba":

(q₀, abcba, Z₀) ⊢ (q₀, bcba, aZ₀)
(q₀, bcba, aZ₀) ⊢ (q₀, cba, baZ₀)
(q₀, cba, baZ₀) ⊢ (q₁, ba, baZ₀) -- see 'c'
(q₁, ba, baZ₀) ⊢ (q₁, a, aZ₀) -- match b
(q₁, a, aZ₀) ⊢ (q₁, ε, Z₀) -- match a
(q₁, ε, Z₀) ⊢ (q₂, ε, Z₀) -- accept!

Pattern 4: Palindromes without Center Marker (NPDA)

Non-deterministic Example

PDA for L = {wwᴿ | w ∈ {a,b}*}

Challenge: The PDA must "guess" where the middle is!

Strategy:

Non-deterministically guess the middle
Before middle: push symbols
After middle: match and pop

Key Transition (non-deterministic):

δ(q₀, ε, X) = {(q₁, X)} -- Guess: "I'm at the middle now!"

This requires non-determinism - the PDA tries all possibilities.

Deterministic vs Non-deterministic PDA

Deterministic PDA (DPDA)

A PDA is deterministic if for every configuration, there is at most ONE possible move:

|δ(q, a, X)| ≤ 1 for all q, a, X
If δ(q, ε, X) is defined, then δ(q, a, X) = ∅ for all a ∈ Σ

Critical Difference from FA!

Unlike Finite Automata where NFA ≡ DFA (equivalent power):

NPDA is strictly MORE powerful than DPDA!

There exist context-free languages that are NOT deterministic context-free.

Comparison

Aspect	DPDA	NPDA
Transitions	At most one choice	Multiple choices possible
Acceptance	Unique computation path	Accept if ANY path accepts
Power	Less powerful	More powerful
Languages	DCFL (subset of CFL)	All CFL
Example NOT accepted	wwᴿ (palindromes)	-

Example

Why wwᴿ needs NPDA

For L = {wwᴿ | w ∈ {a,b}*}:

Consider input "abba"
When reading the second 'b', the PDA doesn't know if it's still in the first half or has entered the second half
It must "guess" - this requires non-determinism

Compare with wcwᴿ: the 'c' marker tells the PDA exactly where the middle is → DPDA suffices.

Equivalence: CFG ↔ PDA

Fundamental Theorem

A language L is context-free if and only if there exists a PDA that accepts L.

CFG and PDA are equivalent in expressive power!

CFG to PDA Construction

Given CFG G = (V, T, P, S), construct PDA M:

Single State PDA

M = ({q}, T, V ∪ T, δ, q, S, ∅)

Use empty stack acceptance.

For each production A → α:

δ(q, ε, A) includes (q, α)

(Replace variable with its production)

For each terminal a:

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

(Match terminal, pop from stack)

Example

Convert CFG to PDA: S → aSb | ε

PDA Transitions:

δ(q, ε, S) = {(q, aSb), (q, ε)}   -- S productions
δ(q, a, a) = {(q, ε)}             -- Match 'a'
δ(q, b, b) = {(q, ε)}             -- Match 'b'
                            

Start stack: S

Accept: when stack is empty

Power and Limitations of PDA

What PDA CAN Do

Recognize all context-free languages
Handle nested structures (parentheses, HTML tags)
Count and match (aⁿbⁿ, aⁿbⁿcⁿ... wait, NOT this!)
Recognize palindromes
Parse programming language syntax

What PDA CANNOT Do

Fundamental Limitation: Single Stack

PDA has only ONE stack, accessed LIFO (Last In, First Out). It cannot:

Keep track of TWO independent counts
Access elements in the middle of the stack
Compare non-adjacent parts of input

Language	PDA?	Reason
L = {aⁿbⁿ \| n ≥ 0}	✓ Yes	Single count, push then pop
L = {aⁿbⁿcⁿ \| n ≥ 0}	✗ No	Need to count a's AND b's vs c's (two counts)
L = {ww \| w ∈ Σ*}	✗ No	Need to compare first and second half
L = {aⁱbʲcᵏ \| i=j or j=k}	✓ Yes	Non-deterministically choose which to match
L = {aⁱbʲcᵏ \| i=j and j=k}	✗ No	Must verify both conditions simultaneously

Exam Note

When asked about limitations, mention:

Single Stack: Only one auxiliary memory, LIFO access
Cannot recognize aⁿbⁿcⁿ: Needs two independent counters
Cannot recognize ww: Needs to remember entire first half and compare
DPDA < NPDA: Some CFLs need non-determinism

Practice Questions

5 Mark Questions

Define PDA. Explain its structure and power. 5 Marks ▼

Definition:

A Push Down Automaton is a 7-tuple P = (Q, Σ, Γ, δ, q₀, Z₀, F) where:

Q = Finite set of states
Σ = Input alphabet
Γ = Stack alphabet
δ = Transition function: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
q₀ = Initial state
Z₀ = Initial stack symbol
F = Set of final states

Structure:

Input tape with read head (left to right)
Finite control (states)
Stack memory (LIFO, unlimited)

Power:

Recognizes all Context-Free Languages
More powerful than FA (can count unboundedly)
Less powerful than TM (only one stack, LIFO access)
Equivalent to CFG in expressive power

Limitations:

Cannot recognize aⁿbⁿcⁿ (needs two counts)
Cannot compare arbitrary substrings

Explain the power and limitations of PDA 5 Marks ▼

Power of PDA:

Recognizes CFLs: All context-free languages can be accepted by a PDA
Stack memory: Provides unlimited auxiliary memory via stack
Handles nesting: Can process nested structures (balanced parentheses)
Counting ability: Can match counts (aⁿbⁿ)
Palindrome recognition: Can recognize palindromes

Limitations of PDA:

Single stack: Only one stack, cannot track multiple independent values
LIFO access: Can only access top of stack, not middle elements
Cannot recognize aⁿbⁿcⁿ: Would need two counters
Cannot recognize ww: Cannot compare arbitrary substrings
DPDA ⊂ NPDA: Some CFLs require non-determinism (wwᴿ without marker)

10 Mark Questions

Design PDA for L = {aⁿb²ⁿ | n ≥ 1} 10 Marks ▼

Strategy:

For each 'a', push TWO markers (X) onto stack
For each 'b', pop ONE marker from stack
Accept when all input consumed and stack has only Z₀

PDA Definition:

Q = {q₀, q₁, q₂}
Σ = {a, b}
Γ = {X, Z₀}
F = {q₂}

Transitions:

δ(q₀, a, Z₀) = {(q₀, XXZ₀)}   -- First 'a': push XX
δ(q₀, a, X)  = {(q₀, XXX)}    -- More 'a's: push XX on X = XXX
δ(q₀, b, X)  = {(q₁, ε)}      -- First 'b': pop X, go to q₁
δ(q₁, b, X)  = {(q₁, ε)}      -- More 'b's: pop X
δ(q₁, ε, Z₀) = {(q₂, Z₀)}     -- Accept when stack has Z₀
                                    

Trace for "aabbbb":

Config	Action
(q₀, aabbbb, Z₀)	Read 'a', push XX
(q₀, abbbb, XXZ₀)	Read 'a', push XX
(q₀, bbbb, XXXXZ₀)	Read 'b', pop X
(q₁, bbb, XXXZ₀)	Read 'b', pop X
(q₁, bb, XXZ₀)	Read 'b', pop X
(q₁, b, XZ₀)	Read 'b', pop X
(q₁, ε, Z₀)	ε-move to accept
(q₂, ε, Z₀)	Accepted!

Design PDA for odd-length palindrome L = {WXWᴿ} over {a,b} 10 Marks ▼

Language: Odd-length palindromes with center marker X

Examples: aXa, abXba, aabXbaa

Strategy:

Phase 1: Push all symbols until X is seen
Phase 2: On seeing X, change state (don't push X)
Phase 3: Match remaining input with stack, pop on match
Accept: When input ends with only Z₀ on stack

PDA Definition:

Q = {q₀, q₁, q₂}
Σ = {a, b, X}
Γ = {a, b, Z₀}
F = {q₂}

Transitions:

-- Phase 1: Push first half
δ(q₀, a, Z₀) = {(q₀, aZ₀)}
δ(q₀, b, Z₀) = {(q₀, bZ₀)}
δ(q₀, a, a)  = {(q₀, aa)}
δ(q₀, a, b)  = {(q₀, ab)}
δ(q₀, b, a)  = {(q₀, ba)}
δ(q₀, b, b)  = {(q₀, bb)}

-- Phase 2: Center marker X (for any stack top)
δ(q₀, X, a) = {(q₁, a)}
δ(q₀, X, b) = {(q₁, b)}
δ(q₀, X, Z₀) = {(q₁, Z₀)}    -- handles XWᴿ where W = ε

-- Phase 3: Match and pop
δ(q₁, a, a) = {(q₁, ε)}
δ(q₁, b, b) = {(q₁, ε)}

-- Accept
δ(q₁, ε, Z₀) = {(q₂, Z₀)}
                                    

Trace for "abXba":

(q₀, abXba, Z₀) ⊢ (q₀, bXba, aZ₀)
(q₀, bXba, aZ₀) ⊢ (q₀, Xba, baZ₀)
(q₀, Xba, baZ₀) ⊢ (q₁, ba, baZ₀) [see X]
(q₁, ba, baZ₀) ⊢ (q₁, a, aZ₀) [match b]
(q₁, a, aZ₀) ⊢ (q₁, ε, Z₀) [match a]
(q₁, ε, Z₀) ⊢ (q₂, ε, Z₀) [accept]

Design PDA for L = {a²ⁿbaⁿ | n ≥ 0} 10 Marks ▼

Language Analysis:

2n 'a's, then one 'b', then n 'a's
Examples: b (n=0), aaba (n=1), aaaabaa (n=2)
First part has TWICE as many 'a's as second part

Strategy:

For each 'a' before 'b': push ONE X
On 'b': change state
For each 'a' after 'b': pop TWO X's
Accept when stack has only Z₀

Transitions:

-- Phase 1: Push for each 'a' before 'b'
δ(q₀, a, Z₀) = {(q₀, XZ₀)}
δ(q₀, a, X)  = {(q₀, XX)}

-- Phase 2: See 'b'
δ(q₀, b, X)  = {(q₁, X)}       -- 'b' seen, go to q₁
δ(q₀, b, Z₀) = {(q₂, Z₀)}     -- n=0 case: just 'b'

-- Phase 3: Pop TWO for each 'a' after 'b'
δ(q₁, a, X)  = {(q₃, ε)}       -- Pop first X
δ(q₃, ε, X)  = {(q₁, ε)}       -- Pop second X (ε-move)

-- Accept
δ(q₁, ε, Z₀) = {(q₂, Z₀)}
                                    

Trace for "aaaabaa" (n=2):

(q₀, aaaabaa, Z₀) ⊢ (q₀, aaabaa, XZ₀)
(q₀, aaabaa, XZ₀) ⊢ (q₀, aabaa, XXZ₀)
(q₀, aabaa, XXZ₀) ⊢ (q₀, abaa, XXXZ₀)
(q₀, abaa, XXXZ₀) ⊢ (q₀, baa, XXXXZ₀)
(q₀, baa, XXXXZ₀) ⊢ (q₁, aa, XXXXZ₀)
(q₁, aa, XXXXZ₀) ⊢ (q₃, a, XXXZ₀) ⊢ (q₁, a, XXZ₀)
(q₁, a, XXZ₀) ⊢ (q₃, ε, XZ₀) ⊢ (q₁, ε, Z₀)
(q₁, ε, Z₀) ⊢ (q₂, ε, Z₀) ✓