Equivalence of CFGs and PDAs

What we are proving

Recall the pieces:

Direction 1: CFG $\Rightarrow$ PDA (the "guess the derivation" PDA)

Formula Construction (single-state PDA)

Build $M$ with one state $q$ , stack start = $S$ , accept by empty stack. HOW, derived step by step:

Why one state? The grammar has no notion of "control state"; all info lives in the sentential form, which we store on the stack. So one state suffices.
Expansion rule — for each grammar rule $A \to \alpha$ : $\delta(q,\varepsilon,A) \ni (q,\alpha)$ (read nothing, pop $A$ , push $\alpha$ ). Why $\varepsilon$ ? Applying a grammar rule consumes no input.
Match rule — for each terminal $a\in\Sigma$ : $\delta(q,a,a) \ni (q,\varepsilon)$ (read $a$ , pop $a$ , push nothing). Why? A terminal on the stack is "promised output"; matching it against real input fulfills the promise.

Worked example

$G$ : $S\to aSb \mid \varepsilon$ generating $\{a^nb^n\}$ , run on $aabb$ Stack shown top-left.

Step	Action (why)	Unread input	Stack
0	start	$aabb$	$S$
1	expand $S\to aSb$ (push RHS)	$aabb$	$aSb$
2	match $a$ (top = next input)	$abb$	$Sb$
3	expand $S\to aSb$	$abb$	$aSbb$
4	match $a$	$bb$	$Sbb$
5	expand $S\to\varepsilon$ (pop $S$ )	$bb$	$bb$
6	match $b$	$b$	$b$
7	match $b$	$\varepsilon$	(empty) → accept

Why this step (step 5)? We guessed the base case of the recursion; nondeterminism explores all guesses, and at least one path accepts iff the string is in $L$ .

Direction 2: PDA $\Rightarrow$ CFG (the "stack-emptying triple" trick)

Intuition WHAT we capture

First normalize $M$ so it accepts by empty stack, every move either pushes exactly one symbol or pops exactly one (no pure replacements), and it has a single accept condition. Then create a variable $==A_{pq}==$ meaning: $A_{pq} \Rightarrow^* w \iff M \text{ can go from state } p \text{ to state } q \text{ reading } w \text{ while net-emptying the stack it touched (starts and ends with the SAME stack height, popping nothing below it).}$ Why this definition? A balanced push-then-eventual-pop on the stack is exactly a bracket structure = exactly what a CFG variable expands to. The "net stack height returns to start" condition is the grammar's recursion mirror.

Formula Grammar rules (derived)

Start variable $S = A_{q_0 q_{\text{accept}}}$ (or $A_{q_0 q}$ over all $q$ for empty-stack accept). Add rules:

Same start/end, no work: $A_{pp}\to\varepsilon$ . Why? Going nowhere reads the empty string with no net stack change.
Split: $A_{pq}\to A_{pr}A_{rq}$ for all states $r$ . Why? If the stack returns to its start height somewhere in the middle (at state $r$ ), the path factors into two balanced sub-runs — a concatenation = two variables.
Match push/pop: if $M$ on reading $a$ from $p$ pushes $t$ moving to $r$ , and on reading $b$ from $s$ pops $t$ moving to $q$ , add $A_{pq}\to a\,A_{rs}\,b.$ Why? The symbol $t$ pushed at the start must be the symbol popped at the very end (it's the "bottom bracket"); everything in between ( $A_{rs}$ ) ran above it without disturbing it.

Common mistakes

Recall

Recall Active recall — cover the answers

What single resource makes both CFGs and PDAs equivalent? → ==a stack (= recursion/nesting)==.
In CFG→PDA, what does the stack hold? → the unmatched suffix of the current sentential form.
When does the CFG→PDA read input? → only when matching a terminal on top of the stack.
What does $A_{pq}\Rightarrow^* w$ mean? → == $M$ goes $p\to q$ on input $w$ with net-zero (balanced) stack usage==.
Why do we get exactly two PDA→CFG rule schemas? → the first pushed symbol is popped either at the very end (match) or earlier (split).

Recall Feynman: explain to a 12-year-old

Imagine you're playing with nesting boxes. A grammar is the recipe: "to make a big box, put a smaller box inside, then close the lid." A PDA is a kid with a stack of plates: every time the recipe says "open a box" the kid puts a plate down; every "close a box" the kid takes a plate off. If the kid ends with no plates left and has read the whole sentence, the sentence followed the recipe. Recipes and the plate-kid can do exactly the same set of patterns — that's the whole theorem. (One pile of plates only! Give the kid two piles and suddenly they can do everything a full computer can.)

A language is context-free iff

it is accepted by some (nondeterministic) pushdown automaton.

The shared structural resource behind CFGs and PDAs

a single stack (grammar recursion ↔ machine stack).

In CFG→PDA, how many states are needed

one state; all information lives on the stack.

CFG→PDA transition for rule A→α

δ(q, ε, A) ∋ (q, α) — read nothing, pop A, push α.

CFG→PDA transition for terminal a

δ(q, a, a) ∋ (q, ε) — read a, pop a, push nothing (match).

Invariant maintained by the CFG→PDA construction

(input read so far) · (stack contents) = current sentential form of a leftmost derivation.

Meaning of variable A_pq in PDA→CFG

strings taking M from state p to q with net-zero (balanced) stack change, never dipping below start height.

PDA→CFG split rule

A_pq → A_pr A_rq (stack returns to start height at intermediate state r).

PDA→CFG match rule

A_pq → a A_rs b, when reading a pushes t (p→r) and reading b pops the same t (s→q).

PDA→CFG base rule

A_pp → ε.

Why two PDA→CFG schemas suffice

first pushed symbol is popped either at the very end (match) or strictly before (split) — exhaustive.

Why nondeterminism is required

deterministic PDAs accept only DCFLs, a strict subset; the PDA must guess the rule/derivation.

What does giving a PDA a second stack do

it becomes as powerful as a Turing machine (no longer just context-free).

Connections

Context-Free Grammars
Pushdown Automata
Chomsky Normal Form
Pumping Lemma for CFLs
Deterministic PDAs and DCFLs
Turing Machines (two-stack PDA = TM)
Closure Properties of CFLs
Leftmost Derivations and Parse Trees

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, idea bahut simple hai: CFG aur PDA dono ek hi cheez ki do shaklein hain. CFG ek recipe hai jo strings banati hai (rules se), aur PDA ek machine hai jisme ek stack hota hai aur woh strings ko pehchanti hai. Theorem kehta hai: koi bhi language context-free hai agar aur sirf agar koi PDA usse accept karta hai. Reason? Grammar me jo recursion/nesting hoti hai (ek variable doosre ke andar expand hota hai), wahi nesting ek stack ke through machine me aa jaati hai.

Direction 1 (CFG → PDA): ek hi state ka PDA banao, stack me start variable $S$ rakho. Agar stack ke top pe variable hai to bina input padhe ( $\varepsilon$ move) usse kisi rule ke right-hand side se replace kar do (push). Agar top pe terminal hai to woh next input symbol se match hona chahiye — dono consume kar do. Jab stack empty aur input khatam ho, to accept. Stack basically "abhi tak jo derive nahi hua" usse hold karta hai. Yaad rakho: expansion me input nahi padhte, sirf matching me padhte hain.

Direction 2 (PDA → CFG): har pair of states $(p,q)$ ke liye ek variable $A_{pq}$ banao jiska matlab hai "machine $p$ se $q$ tak jaa sakti hai aur uss dauraan stack jitna push kiya utna pop bhi ho gaya (balanced)". Bas do tarah ke rules: agar pehla push wala symbol bilkul end me pop hota hai to match rule $A_{pq}\to a\,A_{rs}\,b$ ; agar beech me hi stack apni height pe wapas aa jaata hai to split rule $A_{pq}\to A_{pr}A_{rq}$ . Plus base $A_{pp}\to\varepsilon$ .

Kyun important hai: ye equivalence parsing, compilers, aur language ki theory ki neev hai. Aur ek killer fact yaad rakho — ek stack = context-free, lekin do stacks de do to PDA poora Turing machine ban jaata hai! Aur nondeterminism zaroori hai: deterministic PDA sirf DCFL pakadte hain, poori CFL class nahi.

What we are proving

Direction 1: CFG $\Rightarrow$ PDA (the "guess the derivation" PDA)

Direction 2: PDA $\Rightarrow$ CFG (the "stack-emptying triple" trick)

Common mistakes

Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections