Answer

Theorem: $L$ is accepted by a PDA $\iff$ $L$ is generated by a CFG (i.e., CFL = NPDA languages).

We prove PDA $\rightarrow$ CFG using the Triplet Construction (Sipser / standard textbook method).

---

Given

PDA $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ accepting $L(P)$ by final state (empty stack can be converted).

Assume $\delta$ has no $\epsilon$-transitions on input (can be eliminated). If $\epsilon$-moves exist, handle via closure.

---

Construction of CFG $G = (V, \Sigma, R, S)$

Variables $V$:

• Start symbol $S$
• Triplet variables $[p A q]$ for every $p,q \in Q$ and $A \in \Gamma$
  • Meaning: "Starting in state $p$ with stack top $A$, $P$ can reach state $q$ with $A$ popped off (and any symbols pushed above it matched)."

Productions $R$:

1. Start: $S \rightarrow [q_0 Z_0 p]$ for each $p \in F$

   • Begin at $q_0$ with initial stack $Z_0$, end in any final state $p$.

2. From PDA transitions:
   For every transition $\delta(p, a, A)
   i (q, \alpha)$where$a \in \Sigma \cup {\epsilon}$:

   • Case $\alpha = \epsilon$ (pop $A$, no push):
     $$[p A q] \rightarrow a$$
     (if $a=\epsilon$, RHS is $\epsilon$)

   • Case $\alpha = B_1 B_2 \dots B_k$ ($k \ge 1$):
     For all $r_1, r_2, \dots, r_{k+1} \in Q$:
     $$[p A r_{k+1}] \rightarrow a\; [q B_1 r_1]\; [r_1 B_2 r_2] \dots [r_k B_k r_{k+1}]$$

     • Push $B_1\dots B_k$; must pop them in order via intermediate states.
     • $a$ consumed on transition; each $[r_i B_{i+1} r_{i+1}]$ matches push/pop of $B_{i+1}$.

3. Empty stack (optional, for empty-stack acceptance):
   Add $[p \epsilon p] \rightarrow \epsilon$ for all $p \in Q$ (not needed for final-state).

---

Intuition of Triplet $[p A q]$

• Represents a matching push-pop pair on symbol $A$.
• $p$: state where $A$ is pushed
• $q$: state where $A$ is popped
• The derivation inside $[p A q]$ generates the string read between push and pop of $A$.

---

Proof of Correctness (Sketch)

Soundness (CFG $\subseteq$ PDA):
Every derivation in $G$ corresponds to a valid PDA computation:

• $S \Rightarrow^* [q_0 Z_0 p]$ maps to initial config.
• Production $[p A r] \rightarrow a [q B r_1] \dots$ mimics transition $(p,a,A) \to (q,B\dots)$.
• Base case $[p A q] \rightarrow a$ mimics $(p,a,A) \to (q,\epsilon)$.
• Induction on derivation length shows derived string is accepted by $P$.

Completeness (PDA $\subseteq$ CFG):
For any accepting run of $P$ on $w$, build a parse tree in $G$:

• Root $S \to [q_0 Z_0 p]$.
• Each push of $A$ at state $p$ and corresponding pop at $q$ gives variable $[p A q]$.
• The substring read between push and pop is generated by that variable.
• By induction on height of push-pop pairs, $w$ is generated.

---

Example

PDA for $\{a^n b^n\}$:

• $\delta(q_0, a, Z_0) = (q_0, XZ_0)$
• $\delta(q_0, a, X) = (q_0, XX)$
• $\delta(q_0, b, X) = (q_1, \epsilon)$
• $F = \{q_1\}$

CFG variables: $S, [q_0 Z_0 q_1], [q_0 X q_0], [q_0 X q_1], \dots$
Productions:
$S \rightarrow [q_0 Z_0 q_1]$
$[q_0 X q_1] \rightarrow a [q_0 X q_1] b \mid ab$ (after resolving all intermediate states)
$[q_0 Z_0 q_1] \rightarrow a [q_0 X q_1] b$

Yields $a^n b^n$.

---

Formal Statement

Theorem: $L$ is accepted by a (nondeterministic) PDA iff $L$ is generated by a CFG.
Corollary: CFL = languages accepted by NPDA. DPDA $\subset$ CFL (strict).

---

Final Answer

Proof via Triplet Construction: Create CFG with variables $[p A q]$ representing push-pop of $A$ from state $p$ to $q$. Productions mirror PDA transitions. $S \to [q_0 Z_0 p]$ for final $p$. Induction on derivations/computations proves $L(G) = L(P)$. Hence every PDA language is a CFL.