Equivalence of CFGs and PDAs: Worked examples — Coding deep dive

This page is a drill hall. The parent note built the two constructions; here we run them on every kind of input you could ever meet: normal cases, empty-string edge cases, degenerate grammars, and an exam twist. Before each solution you'll see a Forecast — pause and guess, then check yourself.

Everything here uses only pieces the parent defined: CFGs, PDAs, the single-state "guess-the-derivation" PDA (Direction 1), and the " $A_{pq}$ triple trick" (Direction 2).

The scenario matrix

Think of "every scenario" as a grid. Each row is a class of situation the construction can face; the worked examples below fill in every cell.

Cell	Situation class	What makes it tricky	Covered by
C1	CFG → PDA, ordinary string, accepts	the happy path	Example 1
C2	CFG → PDA, string rejected	a path must exist for no guess	Example 2
C3	CFG → PDA, the empty string $ε$	degenerate input, length 0	Example 3
C4	CFG with a rule having multiple RHS (real branching)	nondeterminism actually matters	Example 4
C5	PDA → CFG, the split rule fires	stack returns to floor mid-run	Example 5
C6	PDA → CFG, the match rule fires	one bracket wraps the whole run	Example 6
C7	Degenerate PDA: empty language / no accepting path	limiting case, $L = \emptyset$	Example 7
C8	Real-world word problem (balanced brackets)	modelling from scratch	Example 8
C9	Exam twist: why determinism breaks here	conceptual trap	Example 9

Read the matrix once. By the end, you'll have seen a live run for each row.

Warm-up conventions (so no symbol is a surprise)

Before any example, pin down exactly how we draw and finish a run — the figure below is our reference for the whole page.

The stack is drawn with its top on the left. So stack aSb means " $a$ is on top, then $S$ , then $b$ at the bottom". In the figure, the leftmost coral box marked TOP is where all the action happens.
$ε$ (epsilon) means the empty string — a string of length zero, "nothing".
"Expand" = replace a variable on top by a rule's right-hand side (reads no input). This is the lavender arrow in the figure.
"Match" = a terminal on top must equal the next input letter; both get consumed. This is the coral arrow in the figure.
Acceptance conventions (both are used on this page, they recognize the same class):
- In the single-state CFG→PDA (Direction 1) we accept by empty stack: a run accepts when the stack is empty AND all input is read. In the reference figure this is the pale-yellow (butter) rounded box on the right, labelled "ACCEPT when…".
- In the PDA→CFG direction (Examples 5–7) we also normalize $M$ to accept by empty stack. When a PDA instead uses accept states, we first convert it to empty-stack acceptance (always possible), so on this page "accept" always means "empty stack + input exhausted".

Study this reference before moving on — every later step ("Match $a$ ", "Expand $S \to \dots$ ") points back to one of these two arrows.

Definition What "

normalized PDA" means (self-contained) Before the PDA→CFG construction we clean the machine so that every single move does exactly one of two simple things:

Push move: read one input symbol (or $ε$ ), and without popping place exactly one new stack symbol on top; or
Pop move: read one input symbol (or $ε$ ), and remove exactly one stack symbol from the top, pushing nothing.

No move is allowed to "replace" (pop-then-push several) or to touch two symbols at once. We also require one start state $q_{0}$ , that the stack starts with a single bottom symbol, and that acceptance is by empty stack. Why bother? With only "up one / down one" moves, the stack-height graph moves in unit steps, so "the stack returns to its starting height" is a crisp, checkable event — and that event is exactly what the $A_{pq}$ variables track. Any PDA can be converted to this form without changing its language.

Formula The two PDA→CFG rule schemas (restated for self-containment)

For a normalized PDA (as defined just above), define the variable $A_{pq}$ meaning: $M$ goes from state $p$ to state $q$ reading some string $w$ , starting and ending at the same stack height, never dipping below that starting height. The grammar's rules are:

Trivial: $A_{pp} \to ε$ — sit still, read nothing, no net stack change.
Split (rule 2): $A_{pq} \to A_{p r} A_{r q}$ for every state $r$ — used when the stack returns to floor at some middle state $r$ .
Match (rule 3): if reading $a$ from $p$ pushes $t$ into state $r$ , and reading $b$ from $s$ pops that same $t$ into $q$ , then $A_{pq} \to a A_{r s} b$ — used when the first symbol pushed is popped only at the very end.

The start variable is $A_{q_{0} q}$ (for empty-stack accept, ranging over end states $q$ ). We refer back to Split and Match by name in Examples 5–7.

Example 1 — C1: the happy path

Worked example Ordinary accepted string

Grammar $G : S \to a S b ∣ ε$ (this is ${a^{n} b^{n}}$ ). Run the Direction-1 PDA on the input $ab$ . Does it accept?

Forecast: $ab$ is $a^{1} b^{1}$ , so it should accept. Guess how many expand steps you'll need before matching. (Hint: how deep is the recursion for $n = 1$ ?)

Start. Stack $= S$ , unread $= ab$ . Why this step? The single-state PDA always starts with just the start variable $S$ on the stack — the "whole thing still to derive".
Expand $S \to a S b$ . Stack $= a S b$ , unread $= ab$ . Why this step? Top is a variable, so we may apply a rule; we guess $a S b$ (the recursive one). This is the lavender expand arrow from the reference figure.
Match $a$ . Stack $= S b$ , unread $= b$ . Why this step? Top is terminal $a$ and next input is $a$ — they agree, so consume both (coral match arrow).
Expand $S \to ε$ . Stack $= b$ , unread $= b$ . Why this step? Top is $S$ ; we guess the base case now (pop $S$ , push nothing).
Match $b$ . Stack empty, unread $= ε$ . Why this step? Top terminal $b$ agrees with the last input letter.

Verify: stack empty and all input consumed ⇒ accept. The derivation we simulated is $S \Rightarrow a S b \Rightarrow ab$ , which indeed produces $ab$ . One expand of the recursive rule, one expand of the base rule = 2 expansions for $n = 1$ . ✓

Example 2 — C2: a rejected string

Worked example String that is NOT in the language

Same $G : S \to a S b ∣ ε$ . Run on $abb$ . Show that no sequence of guesses can accept.

Forecast: $abb$ has one $a$ and two $b$ s — unbalanced, so it must be rejected. But rejection means every nondeterministic path dies. Predict where each path gets stuck.

Start. Stack $= S$ , unread $= abb$ . Why? Standard start.
First guess must be $S \to a S b$ , else we get stuck immediately. Why? If we guess $S \to ε$ now, stack empties but $abb$ is still unread ⇒ dead (can't read input with empty stack).
Stack $= a S b$ , match $a$ ⇒ stack $= S b$ , unread $= bb$ . Why? Only legal move: match the $a$ .
Now top is $S$ . Two guesses:
- Guess $S \to ε$ : stack $= b$ , unread $= bb$ . Match one $b$ ⇒ stack empty, unread $= b$ . Dead (input left, stack empty).
- Guess $S \to a S b$ : stack $= a S bb$ , but next input is $b$ , top is $a$ ⇒ mismatch, dead. Why this step? We enumerate all branches; a rejected string means all branches die.

Verify: every branch dies ⇒ reject. Cross-check with the language: $abb \in / {a^{n} b^{n}}$ since counts differ ( $1 \neq = 2$ ). ✓

Example 3 — C3: the empty string (degenerate, length 0)

Example 4 — C4: genuine branching, nondeterminism does real work

Worked example A rule with multiple right-hand sides

Grammar $G_{2}$ for palindromes-of-even-length over ${a, b}$ that "know the middle": $S \to a S a ∣ b S b ∣ ε .$ Run the Direction-1 PDA on $abba$ .

Forecast: $abba$ read forwards vs backwards is $abba$ vs $abba$ — a palindrome. Predict which rule you pick first, and why guessing is unavoidable.

Start. Stack $= S$ , unread $= abba$ .
Expand $S \to a S a$ (guess, because first input is $a$ ). Stack $= a S a$ , unread $= abba$ . Why this step? We must eventually match the leading $a$ , so the outer bracket should be $a \dots a$ . Nondeterminism lets us try this.
Match $a$ . Stack $= S a$ , unread $= bba$ .
Expand $S \to b S b$ (second input is $b$ ). Stack $= b S ba$ , unread $= bba$ . Why? Inner layer wraps the $b$ s.
Match $b$ . Stack $= S ba$ , unread $= ba$ .
Expand $S \to ε$ . Stack $= ba$ , unread $= ba$ . Why? We reached the middle; base case.
Match $b$ , then match $a$ . Stack empty, unread $= ε$ .

Verify: empty stack + all input read ⇒ accept. Simulated derivation $S \Rightarrow a S a \Rightarrow ab S ba \Rightarrow abba$ . If we had guessed $S \to b S b$ at step 2, top would be $b$ vs input $a$ → mismatch → that branch dies. So nondeterminism is essential: only the correct guess survives. ✓

Example 5 — C5: PDA → CFG where the SPLIT rule fires

Now the other direction. Recall (from the boxed schemas above) the meaning of $A_{pq}$ : " $M$ goes from state $p$ to $q$ reading $w$ , starting and ending at the same stack height, never dipping below it."

The figure below plots stack height against time for two kinds of balanced run. The mint curve on the left touches the floor in the middle — that is precisely the situation the Split rule handles. The coral arch on the right stays above the floor until the very end — that is the Match rule (Example 6). Keep this picture beside you for both examples.

Worked example A run whose stack touches its start-height in the middle

Using the PDA just defined, we want $A_{pp} \Rightarrow^{*} abab$ (two independent blips $ab \cdot ab$ ).

Forecast: The stack returns to floor between the two $ab$ blocks (look at the mint curve dipping to the floor mid-run). Which rule schema covers "returns to floor in the middle" — Split or Match?

Identify the mid-point. After reading the first $ab$ , $M$ is back in state $p$ at the starting stack height — the mint curve's floor-touch. Why this step? The Split schema fires exactly when "the stack hits start height at some middle state $r$ "; here that middle state is $p$ .
Apply Split: $A_{pp} \to A_{pp} A_{pp}$ . Why? The balanced run factors as (first $ab$ )(second $ab$ ), each a balanced sub-run from $p$ to $p$ — a concatenation of two variables.
Each block via Match: the push- $t$ -then-pop- $t$ pair gives $A_{pp} \to a A_{r r} b$ , and $A_{r r} \to ε$ (do-nothing at $r$ ). Why? The pushed $t$ at the start ( $p \to r$ ) is the popped $t$ at the end ( $r \to p$ ) — the outer bracket (coral arch) — with nothing in between, so the middle variable is $A_{r r} \Rightarrow^{*} ε$ .
Derive: $A_{pp} \Rightarrow A_{pp} A_{pp} \Rightarrow (a A_{r r} b) (a A_{r r} b) \Rightarrow (ab) (ab) = abab$ .

Verify: the produced string is $abab$ , length 4, two $ab$ blocks. The split happened because the stack returned to the floor mid-run — exactly cell C5. ✓

Example 6 — C6: PDA → CFG where the MATCH rule wraps the whole run

Worked example One outer bracket encloses everything

Using the PDA just defined, we ask for $A_{pq} \Rightarrow^{*} aabb$ .

Forecast: For $a^{n} b^{n}$ , the first $A$ pushed is the last one popped (innermost recursion pops first, outermost last — the tall coral arch in the s02 figure). So the very first push is matched by the very last pop → which rule?

Recognize the outer bracket. The first $a$ pushes $A$ ; the final $b$ pops that same bottom $A$ — the coral arch that stays above the floor until the end. Why this step? The Match schema fires when a symbol pushed at the very start is popped at the very end, giving $A_{pq} \to a A_{r s} b$ .
Instantiate: push on $a$ keeps state $p$ (so $r = p$ ); pop on $b$ lands in $q$ (so $s = q$ ). This yields the schema $A_{pq} \to a A_{pq} b$ . Why? Reading the PDA above, the recursive middle run is again a balanced $p \to q$ run.
Base case: $A_{pq} \to ε$ when net-zero with no work.
Derive $aabb$ : $A_{pq} \Rightarrow a A_{pq} b \Rightarrow a a A_{pq} b b \Rightarrow aa ε bb = aabb$ .

Verify: output $aabb = a^{2} b^{2} \in {a^{n} b^{n}}$ , and the grammar $A_{pq} \to a A_{pq} b ∣ ε$ is literally the original $S \to a S b ∣ ε$ renamed. The two constructions are inverse in spirit — cell C6 met. ✓

Example 7 — C7: the empty language (limiting / degenerate PDA)

Worked example A PDA that accepts nothing

We work in empty-stack acceptance. What grammar does Direction 2 produce for the PDA above, and what is $L (M)$ ?

Which $A_{pq}$ variables get productive rules? The Trivial rule $A_{pp} \to ε$ is generated for every state by the algorithm, so $A_{q_{0} q_{0}} \to ε$ and $A_{q_{1} q_{1}} \to ε$ both appear. Why this step? The standard PDA→CFG algorithm does emit $A_{pp} \to ε$ unconditionally — we must not pretend it is absent.
So why doesn't $A_{q_{0} q_{0}} \to ε$ leak $ε$ into $L$ ? Because $ε$ enters the language only through the start variable. For empty-stack acceptance the start variable is $A_{q_{0} q}$ where $q$ ranges over states the machine can reach with the stack legally emptied. Why? $A_{q_{0} q_{0}} \to ε$ only witnesses "start at $q_{0}$ , do nothing, stack already at floor" — but the machine's initial configuration has the start stack symbol $⊥$ on the stack, which must still be popped. A do-nothing run does not pop it, so it is not a real accepting run. The rule exists but is not reachable from the true start variable as an accepting derivation.
Prune unreachable / unproductive variables (standard clean-up). After removing variables that cannot be reached from the start variable in an accepting derivation, no production survives that yields any terminal string. Why this step? The CFG↔PDA equivalence is stated up to the usual grammar clean-up (removing useless variables); those leftover $A_{pp} \to ε$ rules are useless here and are pruned, so they introduce no spurious $ε$ .

Verify: $L (M) = \emptyset$ (the empty language, zero strings — different from ${ε}$ which has one string). After clean-up the grammar generates no strings from its start variable. This is the limiting case: a perfectly valid CFL (yes, $\emptyset$ is context-free) with an empty language. ✓

Example 8 — C8: real-world word problem (balanced brackets)

Worked example Matching a code editor's brackets

A text editor must accept exactly the strings of ( and ) that are fully balanced (every open has a matching close, never closing before opening). Build a CFG and trace the Direction-1 PDA on (()).

Forecast: Balanced brackets = classic stack job. Predict the grammar before reading. How many ( on the stack at the deepest point of (())?

Model with a grammar. $S \to (S) S ∣ ε$ (using $($ and $)$ as terminals). Why this step? " $(S) S$ " says: an open bracket, a balanced inside $S$ , its close, then more balanced stuff $S$ . $ε$ = empty is balanced. This is the standard Dyck grammar.
PDA start. Stack $= S$ , unread $= (())$ . Why this step? Direction-1 PDA always begins with the start variable $S$ on the stack.
Expand $S \to (S) S$ ; then Match (. After expand: stack $= (S) S$ , unread $= (())$ . After match: stack $= S) S$ , unread $= ())$ . Why this step? Top is variable $S$ , so we guess the recursive rule (lavender expand); the new top is terminal (, matching the first input bracket (coral match).
Expand inner $S \to (S) S$ ; then Match (. After expand: stack $= (S) S) S$ , unread $= ())$ . After match: stack $= S) S) S$ , unread $=))$ . Why this step? We are now one level deeper — the second ( is the deepest nesting, so two ) are pending below on the stack. We again expand the top $S$ recursively and match the second open bracket, mirroring the increasing nesting depth.
Expand inner $S \to ε$ ; then Match ). After expand: stack $=) S) S$ , unread $=))$ . After match: stack $= S) S$ , unread $=)$ . Why this step? At the deepest point there is nothing more to open, so we guess the base rule $ε$ ; the exposed top ) matches the first close bracket.
Expand $S \to ε$ ; then Match ). After expand: stack $=) S$ , unread $=)$ . After match: stack $= S$ , unread $= ε$ . Why this step? Same base-case guess again exposes the second ), which matches the last close bracket.
Expand $S \to ε$ . Stack empty, unread empty. Why this step? The final trailing $S$ (the "more balanced stuff" slot) contributes nothing here, so the base rule empties the stack.

Verify: balanced ⇒ accept. Sanity: (()) has 2 opens, 2 closes, and no prefix has more ) than ( (running close-minus-open after each symbol: (→−1, ((→−2, (()→−1, (())→0, never positive). ✓ Units check: total opens = total closes = 2. ✓

Example 9 — C9: the exam twist (why determinism fails here)

Worked example "Just make the PDA deterministic" — spot the flaw

A student claims: "For $L = {w w^{R} : w \in {a, b}^{*}}$ (even-length palindromes, where $w^{R}$ is $w$ reversed), I'll build a deterministic PDA that pushes the first half and pops-matches the second half, so CFG↔PDA works deterministically." Where does this argument break, and what's the correct statement?

Forecast: The trap is a hidden guess. Ask: how does the machine know when the middle is?

Locate the guess. To switch from "pushing the first half" to "popping/matching the second half", the PDA must decide "the middle is right here." But no input symbol marks the middle. Why this step? Determinism means the next move is forced by (state, input symbol, stack top). Nothing in that triple tells the machine it has reached the centre — so a deterministic machine cannot know where to flip.
Consequence. ${w w^{R}}$ is a CFL (grammar $S \to a S a ∣ b S b ∣ ε$ , exactly Example 4) but it is not a DCFL — no deterministic PDA accepts it. Why? The equivalence theorem is about nondeterministic PDAs; nondeterminism is precisely what lets the machine "guess the middle" and try every split.
Correct statement. CFG $⟺$ nondeterministic PDA. A deterministic PDA accepts only the strict subclass DCFLs, which does not contain ${w w^{R}}$ . Why this step? This makes the parent's "nondeterminism is essential" mistake concrete: the theorem's PDA side must allow guessing.

Verify: Contrast with Example 8's Dyck language, which is a DCFL — the brackets tell you exactly when to push (() and when to pop ()), so no middle needs guessing. So determinism suffices for balanced brackets but not for ${w w^{R}}$ — pinpointing exactly why the twist is wrong. ✓

Recall

Recall Cover the answers

Reject in a nondeterministic PDA means… ::: every path dies, not just one.
Does the CFG→PDA accept $ε$ for $S \to a S b ∣ ε$ ? ::: Yes — one expand $S \to ε$ empties the stack with no input read.
$\emptyset$ vs ${ε}$ ? ::: $\emptyset$ has zero strings; ${ε}$ has one (the empty string).
When does the PDA→CFG Split rule fire vs Match? ::: Split when the stack returns to floor mid-run; Match when the first push is undone at the very end.
Why doesn't $A_{pp} \to ε$ always add $ε$ to $L$ ? ::: it only counts if $A_{pp}$ is reachable from the start variable in a genuine accepting run; otherwise it is a useless production, pruned.
Why can't ${w w^{R}}$ be done deterministically? ::: nothing in the input marks the middle, so the push→pop switch must be guessed.