Equivalence of CFGs and PDAs

4.6.11 · Coding › Theory of Computation

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

Worked example

$G$ : $S \to a S b ∣ ε$ jo ${a^{n} b^{n}}$ generate karta hai, $aabb$ par run Stack top-left dikhaya gaya hai.

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

Yeh step (step 5) kyun? Humne recursion ka base case guess kiya; nondeterminism saare guesses explore karta hai, aur kam se kam ek path accept karta hai tab aur sirf tab jab string $L$ mein ho.

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

Formula Grammar rules (derived)

Start variable $S = A_{q_{0} q_{accept}}$ (ya empty-stack accept ke liye sabhi $q$ par $A_{q_{0} q}$ ). Rules add karo:

Same start/end, koi kaam nahi: $A_{pp} \to ε$ . Kyun? Kahin nahi jaana empty string padhna hai bina kisi net stack change ke.
Split: $A_{pq} \to A_{p r} A_{r q}$ sabhi states $r$ ke liye. Kyun? Agar stack apni start height par beech mein kahin wapas aati hai (state $r$ par), toh path do balanced sub-runs mein factor hota hai — ek concatenation = do variables.
Match push/pop: agar $M$ $p$ se $a$ padhne par $t$ push karta hai aur $r$ pe jaata hai, aur $s$ se $b$ padhne par $t$ pop karta hai aur $q$ pe jaata hai, toh add karo $A_{pq} \to a A_{r s} b .$ Kyun? Shuru mein push kiya gaya symbol $t$ bilkul aakhir mein pop hona chahiye (woh "bottom bracket" hai); beech mein sab kuch ( $A_{r s}$ ) usse disturb kiye bina uske upar chala.

Recall

Recall Active recall — answers cover karo

Woh ek resource kaunsa hai jo CFGs aur PDAs dono ko equivalent banata hai? → ==a stack (= recursion/nesting)==.
CFG→PDA mein, stack mein kya hota hai? → the unmatched suffix of the current sentential form.
CFG→PDA input kab padhta hai? → only when matching a terminal on top of the stack.
$A_{pq} \Rightarrow^{*} w$ ka kya matlab hai? → == $M$ goes $p \to q$ on input $w$ with net-zero (balanced) stack usage==.
PDA→CFG mein exactly do rule schemas kyun hain? → the first pushed symbol is popped either at the very end (match) or earlier (split).

Recall Feynman: ek 12-saal ke bacche ko samjhao

Socho tum nesting boxes se khel rahe ho. Ek grammar recipe hai: "ek badi box banane ke liye, ek choti box andar rakho, phir lid band karo." Ek PDA ek bachcha hai jiske paas plates ka ek stack hai: jab bhi recipe kehti hai "box kholo" bachcha ek plate neeche rakhta hai; har "box band karo" bachcha ek plate utha leta hai. Agar bachcha koi plate nahi bachi ke saath khatam hota hai aur pura sentence padh chuka hai, toh sentence recipe ke hisaab se tha. Recipes aur plate-bachcha exactly same set of patterns kar sakte hain — yahi poora theorem hai. (Sirf plates ka ek dher! Bachche ko do dher do aur woh achanak sab kuch kar sakta hai jo ek full computer kar sakta hai.)

Ek language context-free hai tab aur sirf tab jab

it is accepted by some (nondeterministic) pushdown automaton.

CFGs aur PDAs ke peeche shared structural resource

a single stack (grammar recursion ↔ machine stack).

CFG→PDA mein kitni states chahiye

one state; all information lives on the stack.

Rule A→α ke liye CFG→PDA transition

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

Terminal a ke liye CFG→PDA transition

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

CFG→PDA construction ka maintain kiya gaya invariant

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

PDA→CFG mein variable A_pq ka matlab

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 → ε.

Do PDA→CFG schemas kyun kaafi hain

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

Nondeterminism kyun zaruri hai

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

PDA ko doosra stack dene se kya hota hai

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

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

What we are proving

Direction 1: CFG ⇒ PDA (the "guess the derivation" PDA)

Direction 2: PDA ⇒ CFG (the "stack-emptying triple" trick)

Common mistakes

Recall

Connections

Concept Map

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

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