Equivalence of CFGs and PDAs: Exercises — Coding deep dive

Intuition How to use this page

Work top to bottom. Each level assumes you have digested Equivalence of CFGs and PDAs — the parent — plus its two constructions:

CFG → PDA (the "guess the leftmost derivation" single-state machine), and
PDA → CFG (the "balanced-run triple" $A_{pq}$ trick). Every problem has a hidden full solution. Try it first, THEN uncover. A quick vocabulary refresher, so we never use a symbol we didn't earn:
$ε$ (epsilon) means the empty string — a string of length zero, "read/write nothing".
$\Rightarrow^{*}$ means "derives in zero or more steps" — apply grammar rules until you reach the target.
$δ (q, a, X) ∋ (r, γ)$ reads as: "in state $q$ , reading input $a$ , with $X$ on top of the stack, the machine MAY move to state $r$ and replace $X$ by the string $γ$ ."
"Top of stack" = the symbol we are allowed to touch right now; the stack grows to the left in our tables.

Level 1 — Recognition

Exercise 1.1 (L1)

State the equivalence theorem precisely, and say which acceptance mode(s) of a PDA are allowed in it.

Recall Solution

Theorem. For any language $L$ : $L$ is context-free $⟺$ $L = L (M)$ for some pushdown automaton $M$ . Acceptance modes. Either acceptance by final state or acceptance by empty stack may be used, because the two modes recognize exactly the same class of languages. We freely convert between them and pick whichever is convenient for a construction.

Exercise 1.2 (L1)

In the CFG → PDA construction, how many states does the machine need, and why that number?

Recall Solution

Exactly one state, call it $q$ . Why. A grammar has no notion of a "control state" — every bit of live information sits inside the current sentential form (the mix of terminals and variables produced so far). We store that sentential form on the stack. Since nothing else needs remembering, one state is enough. The stack does all the work.

Exercise 1.3 (L1)

For the single-state CFG → PDA, write the two transition schemas and label each as "apply rule" or "match input".

Recall Solution

Expansion (apply rule). For every grammar rule $A \to α$ : $δ (q, ε, A) ∋ (q, α) .$ Read no input, pop the variable $A$ , push its right-hand side $α$ . Consumes no input because applying a rule is a paper operation, not a reading operation. Matching (match input). For every terminal $a \in Σ$ : $δ (q, a, a) ∋ (q, ε) .$ Read the input symbol $a$ , pop the matching terminal $a$ , push nothing. This "cashes in" a terminal that the derivation promised.

Level 2 — Application

Exercise 2.1 (L2)

Grammar $G : S \to a S b ∣ ε$ (this generates ${a^{n} b^{n} : n \geq 0}$ ). Using the single-state PDA, trace the run on the input $ab$ . Show unread input and stack at every step, and mark whether the run accepts.

Recall Solution

Stack shown top-left; accept = empty stack with all input read.

Step	Action (why)	Unread input	Stack
0	start	$ab$	$S$
1	expand $S \to a S b$ (push RHS)	$ab$	$a S b$
2	match $a$ (top = next input)	$b$	$S b$
3	expand $S \to ε$ (pop $S$ )	$b$	$b$
4	match $b$	$ε$	(empty) → accept

The accepting path exists, so $ab \in L (M)$ . Nondeterminism explored the guess "use base case now" at step 3.

Exercise 2.2 (L2)

Same $G$ and PDA, input $aab$ (note: unbalanced). Argue that no path accepts.

Recall Solution

Every expansion of $S$ either produces $a S b$ (one $a$ before and one $b$ after the recursive $S$ ) or produces $ε$ . So any string derived has the form $a^{n} b^{n}$ : the count of $a$ 's equals the count of $b$ 's and all $a$ 's precede all $b$ 's. $aab$ has two $a$ 's and one $b$ — the counts differ. On the stack side: to match the two leading $a$ 's we must expand $S \to a S b$ twice, leaving at least $S bb$ or $bb$ over the tail, i.e. at least two $b$ 's owed, but only one $b$ remains in the input. Some $b$ on the stack can never be matched, so the stack cannot empty. No accepting path exists ⇒ $aab \in / L (M)$ . ✓ (consistent with $aab \in / {a^{n} b^{n}}$ ).

Exercise 2.3 (L2)

For $G : S \to (S) ∣ S S ∣ ε$ (balanced parentheses), write out all transitions of the single-state PDA. Then trace input ().

Recall Solution

Terminals are ( and ); treat them as two stack terminals. Variable: $S$ . Expansion transitions (read $ε$ ): $δ (q, ε, S) ∋ (q, (S)), δ (q, ε, S) ∋ (q, S S), δ (q, ε, S) ∋ (q, ε) .$ Match transitions (read the terminal): $δ (q, (, () ∋ (q, ε), δ (q,),)) ∋ (q, ε) .$ Trace on ():

Step	Action	Unread input	Stack
0	start	`()`	$S$
1	expand $S \to (S)$	`()`	`(` $S$ `)`
2	match `(`	`)`	$S$ `)`
3	expand $S \to ε$	`)`	`)`
4	match `)`	$ε$	empty → accept

Level 3 — Analysis

Exercise 3.1 (L3)

State the loop invariant of the CFG → PDA construction and use it to explain, in one sentence each, why acceptance implies $w \in L (G)$ and $w \in L (G)$ implies acceptance.

Recall Solution

Invariant. At every moment of a run, $(input already read) \cdot (stack contents, top first) = a sentential form of a leftmost derivation of G .$ Accept ⇒ $w \in L (G)$ : if the run ends with empty stack and all of $w$ read, the invariant says $w \cdot ε = w$ is a sentential form containing no variables — i.e. a fully derived terminal string — so $S \Rightarrow^{*} w$ , hence $w \in L (G)$ . $w \in L (G)$ ⇒ accept: take a leftmost derivation of $w$ ; at each step the PDA can mirror it (expansion for a rule application, match for the exposed terminal), and nondeterminism guarantees this exact sequence of guesses is one available path, ending with empty stack.

Exercise 3.2 (L3)

In the PDA → CFG construction, the variable $A_{pq}$ means " $M$ goes from state $p$ to state $q$ reading some $w$ , with net-zero balanced stack usage." A student claims $A_{pq}$ just means " $q$ is reachable from $p$ ." Give a concrete reason this is wrong.

Recall Solution

"Reachable" allows the machine to pop symbols that were on the stack before $p$ — dipping below the starting stack height. That path leaves the stack lower than it started, so it does not correspond to a balanced bracket structure and is not what a single grammar variable can encode. Concretely: suppose from $p$ the only move is "pop $X$ (which was already there) → $q$ ". Then $q$ is reachable from $p$ , but the run consumed a symbol it did not itself push, so $A_{pq} \Rightarrow^{*} ε$ must not hold. If we treated $A_{pq}$ as mere reachability, the grammar would generate strings the PDA never accepts. The balanced (never-dip-below-start) condition is exactly what makes the run mirror the nesting of grammar rules.

Exercise 3.3 (L3)

Prove that the two PDA → CFG rule schemas — split $A_{pq} \to A_{p r} A_{r q}$ and match $A_{pq} \to a A_{r s} b$ — are exhaustive: every balanced run is covered by exactly one case. Use the figure.

Recall Solution

Take any balanced run from $p$ to $q$ on non-empty input (the empty case is handled by $A_{pp} \to ε$ ). Look at the very first symbol $t$ that this run pushes onto the stack (red in the figure). Because the run is balanced (ends at the same height it started, never dipping below), $t$ must be popped again at some point. Two — and only two — possibilities:

$t$ is popped only at the very last step of the run. Then the push at the start and the pop at the end are the outer bracket; everything strictly between them ran above $t$ without touching it — a balanced sub-run from the post-push state $r$ to the pre-pop state $s$ . This is the match rule $A_{pq} \to a A_{r s} b$ .
$t$ is popped strictly before the end, at some intermediate state $r$ . At that moment the stack is back to its starting height. So the whole run factors into two consecutive balanced runs: $p \to r$ and $r \to q$ . This is the split rule $A_{pq} \to A_{p r} A_{r q}$ . There is no third option: the height either returns to start for the first time at the end (case 1) or earlier (case 2). Hence the schemas are exhaustive and non-overlapping. $■$

Level 4 — Synthesis

Exercise 4.1 (L4)

Build a single-state PDA (by empty stack) for $L = {a^{i} b^{j} : j = 2 i, i \geq 0}$ by first writing a CFG, then applying the CFG → PDA construction. Trace $abb$ .

Recall Solution

CFG. Each $a$ must contribute two $b$ 's at the end: $S \to a S bb ∣ ε$ . PDA (single state $q$ , start symbol $S$ , accept by empty stack). Expansion: $δ (q, ε, S) ∋ (q, a S bb)$ and $δ (q, ε, S) ∋ (q, ε)$ . Match: $δ (q, a, a) ∋ (q, ε)$ , $δ (q, b, b) ∋ (q, ε)$ . Trace on $abb$ :

Step	Action	Unread input	Stack
0	start	$abb$	$S$
1	expand $S \to a S bb$	$abb$	$a S bb$
2	match $a$	$bb$	$S bb$
3	expand $S \to ε$	$bb$	$bb$
4	match $b$	$b$	$b$
5	match $b$	$ε$	empty → accept

$i = 1, j = 2 = 2 i$ . ✓

Exercise 4.2 (L4)

Take the two-state PDA for ${a^{n} b^{n}}$ from the parent (push $A$ per $a$ in state $p$ ; on the first $b$ pop $A$ and move to $q$ ; pop $A$ per further $b$ in $q$ ). Apply the PDA → CFG match schema to recover a grammar, and confirm it is essentially $S \to a S b ∣ ε$ .

Recall Solution

On reading $a$ in $p$ the machine pushes $A$ and stays in $p$ . On reading $b$ the machine pops $A$ — from $p$ moving to $q$ , or from $q$ staying in $q$ . Consider the balanced run recognized by $A_{pq}$ . Match schema $A_{pq} \to a A_{r s} b$ where "push $t = A$ on $a$ , state $p \to r$ " gives $r = p$ , and "pop $t = A$ on $b$ , state $s \to q$ " gives $s = p$ (the inner balanced run must end just before that final pop, in state $p$ ). So: $A_{pq} \to a A_{pq} b .$ Base case $A_{pp} \to ε$ (going nowhere, empty string, no net stack change). But an empty outer run also collapses $A_{pq}$ : the smallest balanced run reading $ε$ that starts pushing then immediately... — concretely the derivation bottoms out with $A_{pq} \Rightarrow ε$ via the $n = 0$ path. Renaming $A_{pq} = S$ : $S \to a S b ∣ ε .$ This is exactly the original grammar — the two constructions are inverse in spirit. ✓

Level 5 — Mastery

Exercise 5.1 (L5)

Explain precisely why a two-stack PDA is strictly more powerful than a one-stack PDA, and connect this to why the CFG↔PDA equivalence is special to exactly one stack.

Recall Solution

A two-stack PDA can simulate a Turing machine: let the first stack hold the tape contents to the left of the head (top = cell nearest the head) and the second stack hold the tape to the right. Moving the head right = pop from the right stack, push onto the left stack; moving left = the reverse. Reading/writing the current cell = inspecting/replacing the top of one stack. Two stacks thus give unrestricted read-write access to an unbounded tape — full Turing power. Hence two-stack machines recognize all recursively enumerable languages, far beyond context-free. The CFG↔PDA theorem hinges on a single stack because one stack encodes exactly one level of bracketed nesting — matching the single-layer recursion of a CFG's derivations. Add a second independent stack and you get two coordinated counters (or a tape), escaping the family. So "context-free = one stack" is a knife-edge, not a general "more memory, same class" trend.

Exercise 5.2 (L5)

Let $L_{1} = {a^{n} b^{n} c^{m}}$ and $L_{2} = {a^{n} b^{m} c^{m}}$ (both context-free). Is $L_{1} \cap L_{2} = {a^{n} b^{n} c^{n}}$ context-free? Use it to conclude a closure fact.

Recall Solution

$L_{1} \cap L_{2} = {a^{n} b^{n} c^{n} : n \geq 0}$ . By the pumping lemma for CFLs, ${a^{n} b^{n} c^{n}}$ is not context-free: any pump-decomposition $uv x y z$ with $∣ v x y ∣ \leq p$ can touch at most two of the three letter-blocks, so pumping unbalances the third. Therefore $L_{1} \cap L_{2}$ is not context-free even though $L_{1}, L_{2}$ are. Closure conclusion: context-free languages are not closed under intersection. (See Closure Properties of CFLs.) Contrast: regular languages are, and a single PDA cannot simultaneously enforce two independent balance conditions — again the "one stack" limit at work.

Exercise 5.3 (L5)

A student says: "Since every CFG has an equivalent PDA, and PDAs can be made deterministic, every context-free language is deterministic (a DCFL)." Diagnose the error precisely.

Recall Solution

The equivalence theorem produces a nondeterministic PDA, and its "guess the derivation" step is essential: the machine must guess which rule to apply / where to split. Nondeterministic PDAs recognize all context-free languages, but deterministic PDAs recognize only a proper subset, the DCFLs. Counterexample: $L = {w w^{R} : w \in {a, b}^{*}}$ (even-length palindromes) is context-free but not a DCFL — a deterministic machine cannot know where the string's midpoint is without guessing. So you cannot always determinize a PDA while preserving its language. The claim conflates the two machine classes. ✗

Final Recall

Recall Cover the answers

The stack in CFG→PDA holds… ::: the unmatched suffix of the current leftmost sentential form. CFG→PDA consumes input only when… ::: matching a terminal on top of the stack (expansions read $ε$ ). $A_{pq} \Rightarrow^{*} w$ means… ::: $M$ goes $p \to q$ on $w$ with net-zero, never-dip-below-start (balanced) stack use. The two PDA→CFG schemas are exhaustive because… ::: the first pushed symbol is popped either at the very end (match) or earlier (split). Two stacks give… ::: full Turing power (tape = left stack + right stack), leaving the CFL class. Determinization fails for PDAs because… ::: DCFL is a proper subset of CFL; the subset construction can't track unbounded stacks.