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

4.6.10 · Coding › Theory of Computation

WHAT is a PDA?

WHY $δ$ ka yeh signature hai: kisi bhi moment pe machine dekhti hai (current state, agla input symbol ya kuch nahi, stack ke top pe symbol). Uska response ek set hota hai (new state, push karne wali string) — ek set isliye kyunki PDAs nondeterministic hote hain, aur $ε$ -input use karke woh input consume kiye bina stack ko rearrange kar sakti hai.

Configuration (Instantaneous Description, ID)

WHY yeh triple: yeh exactly woh information hai jo machine ka poora future determine karne ke liye chahiye — jo input already padha ja chuka hai usse koi matlab nahi, sirf jo bacha hai aur jo memory mein hai woh matter karta hai.

DO acceptance modes

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

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

Idea: har $a$ ke liye ek $A$ push karo, har $b$ ke liye ek $A$ pop karo. Stack exactly tab empty hogi jab counts match karein.

States ${q}$ , $Z_{0}$ = bottom. Transitions:

$δ (q, a, Z_{0}) = {(q, A Z_{0})}$ — Kyun? pehla $a$ : bottom marker ke upar $A$ push karo.
$δ (q, a, A) = {(q, AA)}$ — Kyun? har agle $a$ ke liye: ek aur $A$ push karo (count up).
$δ (q, b, A) = {(q, ε)}$ — Kyun? har $b$ ke liye: ek $A$ pop karo (ek $a$ ko match karo).
$δ (q, ε, Z_{0}) = {(q, ε)}$ — Kyun? barabar $a$ 's aur $b$ 's ke baad $A$ 's khatam ho jaate hain; $Z_{0}$ pop karo ⇒ empty stack ⇒ accept.

$aabb$ pe run: $(q, aabb, Z_{0}) ⊢ (q, abb, A Z_{0}) ⊢ (q, bb, AA Z_{0}) ⊢ (q, b, A Z_{0}) ⊢ (q, ε, Z_{0}) ⊢ (q, ε, ε) ✓$ Yeh step (last) kyun: rule 4 $ε$ -input pe marker ko pop karta hai, empty stack bacha ke → empty stack se accept.

Worked Example 2 — same language by final state

Rules 1–3 rakho, lekin $Z_{0}$ dump karne ki jagah, use check karo: 4'. $δ (q, ε, Z_{0}) = {(q_{f}, Z_{0})}$ — final state $q_{f}$ mein move karo jab sirf marker bacha ho. $F = {q_{f}}$ set karo. Popping kyun nahi? Final-state acceptance stack ko ignore karta hai; humein sirf $q_{f}$ mein hona chahiye jab input poora padh liya ho.

$aabb$ pe run khatam hota hai $(q, ε, Z_{0}) ⊢ (q_{f}, ε, Z_{0})$ , $q_{f} \in F$ → accept. ✓

Worked Example 3 — palindromes ${w w^{R}}$ (nondeterminism zaroori hai)

$L = {w w^{R} ∣ w \in {a, b}^{*}}$ ke liye PDA guess karta hai midpoint:

Phase 1: har input symbol push karo.
$ε$ -move: guess karo "hum abhi middle pe hain."
Phase 2: pop karna current input se match karna chahiye.

Nondeterministic kyun? Ek deterministic PDA unmarked middle detect nahi kar sakta. Yeh dikhata hai DPDA ⊊ PDA: nondeterministic PDAs strictly zyada strong hote hain.

Common mistake Steel-manned pitfalls

Mistake A: "Final-state acceptance mein bhi empty stack chahiye." Kyun sahi lagta hai: dono modes kai examples mein (jaise Ex.1) saath "finish" hote hain. Fix: definition ke hisaab se $L_{F}$ $γ$ ko ignore karta hai. Tum stack pe junk hote hue bhi accept kar sakte ho.

Mistake B: "Stack top ID mein sabse right symbol hota hai." Kyun sahi lagta hai: hum input left→right padhte hain. Fix: convention ke mutabik stack ka top $γ$ mein sabse left likha jaata hai, toh $A β$ ka matlab hai $A$ top pe hai. Ise ulta karne se har transition toot jaata hai.

Mistake C: "DPDA = PDA, bilkul jaise DFA = NFA." Kyun sahi lagta hai: finite automata ke liye determinism mein koi cost nahi. Fix: stack subset-construction trick ko todti hai. DPDAs strictly weaker hote hain ( ${w w^{R}}$ unhe alag karta hai).

Mistake D: "Empty stack matlab stack mein literally zero symbols hain including $Z_{0}$ ." Fix: haan — $L_{N}$ ke liye tumhe $Z_{0}$ bhi pop karna hoga. Isliye conversions mein ek fresh marker $X_{0}$ use se neeche add kiya jaata hai taaki simulated machine kabhi jaldi empty na ho.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Sochoh ek robot letters ki ek strip padh raha hai. Robot ke paas ek chhota sa brain hai (kuch moods) aur plates ka ek stack. Jab woh koi letter dekhta hai toh woh ek plate upar rakh sakta hai ya top wali plate utha sakta hai. Yeh check karne ke liye ki "har open bracket ka ek close bracket hai," woh har ( ke liye ek plate neeche rakhta hai aur har ) ke liye ek uthaa leta hai. Agar end mein saari plates khatam ho jaayein, toh brackets match kiye! "Empty stack = accept" matlab koi plate nahi bachi. "Final state = accept" matlab robot ek khush mood mein khatam hota hai, plates ki parwah kiye bina. "Tum pass ho gaye" kehne ke do tarike, same power.

Flashcards

PDA ka 7-tuple banane ke liye NFA mein kaunse 5 components add hote hain (NFA se extra)?

Γ

(stack alphabet) aur

Z_{0}

(initial stack symbol) — stack machinery;

δ

ab stack top bhi read/write karta hai.

PDA configuration (ID) teen cheezein ki triple hoti hai — kaunsi?

(current state, remaining input, poori stack contents jisme top sabse left ho).

(p, γ) \in δ (q, a, A)

diya hua ho toh one-step "yields" rule likhao.

(q, a w, A β) ⊢ (p, w, γ β)

Empty stack se acceptance define karo.

w

accept hota hai agar

(q_{0}, w, Z_{0}) ⊢^{*} (q, ε, ε)

; final states irrelevant hain.

Final state se acceptance define karo.

w

accept hota hai agar

(q_{0}, w, Z_{0}) ⊢^{*} (q, ε, γ)

jahan

q \in F

ho; stack contents ignore hoti hain.

Kya empty-stack aur final-state PDAs equally powerful hain?

Haan — dono exactly context-free languages accept karte hain; ek doosre mein convert ho sakta hai.

Empty-stack→final-state safely convert karne ki trick?

Z_{0}

ke neeche ek fresh bottom marker

X_{0}

add karo taaki machine kabhi accidentally empty na ho; jab

X_{0}

surface aaye toh final state reach ho.

δ

ka output finite subset of

Q \times Γ^{*}

kyun hota hai?

Kyunki PDAs nondeterministic hote hain (multiple moves) aur ek move poori string push kar sakta hai.

PDAs regular languages ko kyun beat karte hain?

Unbounded LIFO stack nested structure count/match kar sakta hai (jaise

a^{n} b^{n}

) jo finite states akele nahi kar sakte.

Kya deterministic PDAs utne hi powerful hain jitne nondeterministic wale?

Nahi — DPDA ⊊ PDA; jaise

{w w^{R}}

ke liye nondeterministic midpoint guessing chahiye.

ID mein stack ka top kahan likha jaata hai?

Stack string

γ

mein sabse left.

"Pop"

δ

mein kaise express hota hai?

Top

A

ε

se replace karo:

δ (q, a, A) ∋ (p, ε)

Connections

Context-Free Grammars — PDAs ke equivalent hain (CFG ⇄ PDA conversions).
Pumping Lemma for CFLs — PDAs kya accept karte hain uski limits.
Nondeterministic Finite Automata — PDA = NFA + stack.
Turing Machines — LIFO stack ko 2-way tape se replace karo ⇒ zyada power.
Deterministic PDA (DPDA) — strict subclass; LR parsing ka basis.
Closure Properties of CFLs