Pushdown automata (PDA) — configuration, acceptance by empty stack - final state

WHAT is a PDA?

WHY $\delta$ has this signature: at any moment the machine sees (current state, next input symbol or nothing, symbol on top of stack). Its response is a set of (new state, string to push) — a set because PDAs are nondeterministic, and possibly using $\varepsilon$ -input so it can rearrange the stack without consuming input.

Configuration (Instantaneous Description, ID)

WHY this triple: it is exactly the information needed to determine the machine's whole future — nothing about already-read input matters, only what's left and what's in memory.

The TWO acceptance modes

Figure — Pushdown automata (PDA) — configuration, acceptance by empty stack - final state

Worked Example 1 — $L=\{a^n b^n \mid n\ge 1\}$ by empty stack

Idea: push one $A$ per $a$ , pop one $A$ per $b$ . Stack empties exactly when counts match.

States $\{q\}$ , $Z_0$ = bottom. Transitions:

$\delta(q,a,Z_0)=\{(q,AZ_0)\}$ — Why? first $a$ : push $A$ above bottom marker.
$\delta(q,a,A)=\{(q,AA)\}$ — Why? each further $a$ : push another $A$ (count up).
$\delta(q,b,A)=\{(q,\varepsilon)\}$ — Why? each $b$ : pop one $A$ (match one $a$ ).
$\delta(q,\varepsilon,Z_0)=\{(q,\varepsilon)\}$ — Why? after equal $a$ 's and $b$ 's the $A$ 's are gone; pop $Z_0$ ⇒ empty stack ⇒ accept.

Run on $aabb$ : $(q,aabb,Z_0)\vdash(q,abb,AZ_0)\vdash(q,bb,AAZ_0)\vdash(q,b,AZ_0)\vdash(q,\varepsilon,Z_0)\vdash(q,\varepsilon,\varepsilon)\ \checkmark$ Why this step (last): rule 4 pops the marker on $\varepsilon$ -input, leaving empty stack → accept by empty stack.

Worked Example 2 — same language by final state

Keep rules 1–3, but instead of dumping $Z_0$ , check it: 4'. $\delta(q,\varepsilon,Z_0)=\{(q_f,Z_0)\}$ — move to final state $q_f$ when only the marker remains. Set $F=\{q_f\}$ . Why no popping? Final-state acceptance ignores the stack; we only need to be in $q_f$ with input fully read.

Run on $aabb$ ends $(q,\varepsilon,Z_0)\vdash(q_f,\varepsilon,Z_0)$ , $q_f\in F$ → accept. ✓

Worked Example 3 — palindromes $\{ww^R\}$ (nondeterminism is essential)

For $L=\{w w^R \mid w\in\{a,b\}^*\}$ the PDA guesses the midpoint:

Phase 1: push each input symbol.
$\varepsilon$ -move: guess "we're at the middle now."
Phase 2: pop must match current input.

Why nondeterministic? A deterministic PDA cannot detect the unmarked middle. This shows DPDA ⊊ PDA: nondeterministic PDAs are strictly stronger.

Common mistake Steel-manned pitfalls

Mistake A: "Final-state acceptance also requires empty stack." Why it feels right: both modes "finish" together in many examples (like Ex.1). Fix: by definition $L_F$ ignores $\gamma$ . You can accept with junk still on the stack.

Mistake B: "The stack top is the rightmost symbol in the ID." Why it feels right: we read input left→right. Fix: by convention top of stack is written leftmost in $\gamma$ , so $A\beta$ means $A$ is on top. Reversing it breaks every transition.

Mistake C: "DPDA = PDA, just like DFA = NFA." Why it feels right: for finite automata determinism costs nothing. Fix: the stack breaks the subset-construction trick. DPDAs are strictly weaker ( $\{ww^R\}$ separates them).

Mistake D: "Empty stack means stack literally has zero symbols including $Z_0$ ." Fix: yes — for $L_N$ you must pop $Z_0$ too. That's why conversions add a fresh marker $X_0$ below it so the simulated machine never empties early.

Recall Feynman: explain to a 12-year-old

Imagine a robot reading a strip of letters. The robot has a small brain (a few moods) and a stack of plates. When it sees a letter it can put a plate on top or take the top plate off. To check that "every open bracket has a close bracket," it puts a plate down for each ( and takes one off for each ). If at the end the plates are all gone, the brackets matched! "Empty stack = accept" means no plates left. "Final state = accept" means the robot ends in a happy mood, no matter the plates. Two ways to say "you passed," same power.

Flashcards

What 5 components does an NFA gain to become a PDA's 7-tuple (extras over an NFA)?

\Gamma

(stack alphabet) and

Z_0

(initial stack symbol) — the stack machinery;

\delta

now also reads/writes the stack top.

A PDA configuration (ID) is a triple of what?

(current state, remaining input, full stack contents with top leftmost).

Write the one-step "yields" rule given

(p,\gamma)\in\delta(q,a,A)

(q,aw,A\beta)\vdash(p,w,\gamma\beta)

Define acceptance by empty stack.

w

accepted iff

(q_0,w,Z_0)\vdash^*(q,\varepsilon,\varepsilon)

; final states irrelevant.

Define acceptance by final state.

w

accepted iff

(q_0,w,Z_0)\vdash^*(q,\varepsilon,\gamma)

with

q\in F

; stack contents ignored.

Are empty-stack and final-state PDAs equally powerful?

Yes — both accept exactly the context-free languages; each converts to the other.

Trick used to convert empty-stack→final-state safely?

Add a fresh bottom marker

X_0

below

Z_0

so the machine never empties accidentally; reach a final state when

X_0

surfaces.

Why is

\delta

's output a finite subset of

Q\times\Gamma^*

Because PDAs are nondeterministic (multiple moves) and a move can push a whole string.

Why do PDAs beat regular languages?

The unbounded LIFO stack can count/match nested structure (e.g.

a^nb^n

) that finite states alone cannot.

Are deterministic PDAs as powerful as nondeterministic ones?

No — DPDA ⊊ PDA; e.g.

\{ww^R\}

needs nondeterministic midpoint guessing.

In an ID, where is the top of stack written?

Leftmost in the stack string

\gamma

How is a "pop" expressed in

\delta

Replace top

A

\varepsilon

\delta(q,a,A)\ni(p,\varepsilon)

Connections

Context-Free Grammars — equivalent to PDAs (CFG ⇄ PDA conversions).
Pumping Lemma for CFLs — limits of what PDAs accept.
Nondeterministic Finite Automata — PDA = NFA + stack.
Turing Machines — replace LIFO stack with a 2-way tape ⇒ more power.
Deterministic PDA (DPDA) — strict subclass; basis of LR parsing.
Closure Properties of CFLs

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, PDA ka pura funda simple hai: ek NFA le lo aur usme ek stack jod do. NFA akela sirf utna hi yaad rakh sakta hai jitne uske states hain — yani fixed memory. Lekin stack ek aisi memory hai jo unbounded hai par LIFO (last-in-first-out) tareeke se chalti hai. Isi ek addition ki wajah se PDA regular languages se aage badhkar context-free languages pehchaanne lagta hai, jaise $a^n b^n$ jisme tumhe count karna padta hai.

Configuration (ID) matlab machine ki ek snapshot — teen cheezein: kaunse state mein ho, kitna input bacha hai, aur stack mein abhi kya pada hai (top symbol sabse left mein likhte hain, yeh convention yaad rakhna). Har move mein ek input letter consume hota hai (ya $\varepsilon$ pe bina consume kiye), aur stack ka top symbol kisi string se replace ho jaata hai — push, pop, ya peek, sab isi ek rule ke special cases hain.

Acceptance ke do tareeke hain. Final state se: saara input padhne ke baad agar tum kisi accepting state mein ho to accept — stack mein kuch bhi pada ho, koi farak nahi. Empty stack se: saara input padhne ke baad agar stack bilkul khaali (including $Z_0$ ) ho to accept — final state ki zarurat nahi. Mast baat yeh hai ki dono bilkul same power rakhte hain, dono exactly CFLs accept karte hain, aur ek se dusre mein convert kar sakte ho (ek fresh bottom marker $X_0$ laga ke).

Ek important caution: NFA aur DFA toh equal power ke hote hain, par PDA mein aisa nahi — deterministic PDA strictly kamzor hota hai. Jaise palindrome $ww^R$ ko pehchanne ke liye machine ko beech ka point "guess" karna padta hai, jo sirf nondeterminism se hota hai. Yeh exam mein bahut poocha jaata hai!

Pushdown automata (PDA) — configuration, acceptance by empty stack - final state

WHAT is a PDA?

Configuration (Instantaneous Description, ID)

The TWO acceptance modes

Worked Example 1 — $L=\{a^n b^n \mid n\ge 1\}$ by empty stack

Worked Example 2 — same language by final state

Worked Example 3 — palindromes $\{ww^R\}$ (nondeterminism is essential)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections