Context-free grammars (CFG) — productions, derivations, parse trees: Worked examples

The scenario matrix

Every CFG exercise you meet is one of these case classes. We will hit each one.

Cell	Case class	What makes it tricky	Example
C1	Balanced / nested structure	needs a stack — DFAs fail	Ex 1: `(()())`
C2	Equal-count language $a^{n} b^{n}$	counting two things in lockstep	Ex 2
C3	The degenerate case $ε$	empty string, zero-length yield	Ex 3
C4	Two-sided count / palindrome-like	symmetry around a centre	Ex 4: $a^{n} b^{2 n}$
C5	Ambiguity detection	≥2 parse trees for one string	Ex 5
C6	Ambiguity removal (precedence)	rewrite so each string has one tree	Ex 6
C7	Leftmost = rightmost = tree	ordering vs structure	Ex 7
C8	Word problem (real syntax)	model something real as a CFG	Ex 8: if/else
C9	Exam twist — union of counts	one grammar, several sub-cases	Ex 9: $a^{i} b^{j} c^{k}, i = j$ or $j = k$

Terminals we use are the actual letters like $a$ , $b$ , $($ , $)$ . Variables are capitals like $S, A, E$ . A production $A \to α$ means "wherever you see $A$ , you may swap in $α$ ". Recall $\Rightarrow$ is one swap and $\Rightarrow^{*}$ is "zero or more swaps".

C1 — Nested & balanced structure

Worked example Derive

(()()) in $G_{1} : S \to (S) S ∣ ε$ Forecast: Guess how many times you must apply $S \to (S) S$ before finishing. (Hint: count the opening parentheses.)

There are 3 ( in the string, so we expand $S \to (S) S$ exactly three times, then erase the leftovers with $S \to ε$ .

$S \Rightarrow (S) S$ — Why? We need the outermost (...), so use the recursive rule.
$\Rightarrow (S)$ — Why? After the outer group there is nothing left, so kill the trailing $S$ with $S \to ε$ .
$\Rightarrow ((S) S)$ — Why? Inside the first pair we see ()(): two sibling groups. Expand the inner $S$ once → this makes room for a first group and a trailing $S$ for the second.
$\Rightarrow (() S)$ — Why? That first inner $S$ is empty, so $S \to ε$ .
$\Rightarrow (() (S) S)$ — Why? The trailing $S$ must become the second group (), so expand it with $S \to (S) S$ .
$\Rightarrow (() () S)$ then $\Rightarrow (() ())$ — Why? Both remaining $S$ 's are empty; apply $S \to ε$ twice.

Look at the parse tree below — the shape is the nesting.

Verify: The yield read left-to-right is (()()). Count check: ( appears 3 times, ) appears 3 times, and at every prefix the running count of ( minus ) never goes negative → it is balanced. ✓

C2 — Equal counts $a^{n} b^{n}$

Worked example Show

aaabbb $\in L (G_{2})$ , where $G_{2} : S \to a S b ∣ ε$ Forecast: Each rule application adds one a on the left and one b on the right. How many applications of $S \to a S b$ for aaabbb?

Three a's means 3 applications, then one $ε$ .

$S \Rightarrow a S b$ — Why? $S \to a S b$ wraps the current string with one matching pair. This guarantees counts stay equal.
$\Rightarrow aa S bb$ — Why? Wrap again; still balanced.
$\Rightarrow aaa S bbb$ — Why? Third wrap → now three of each are locked in.
$\Rightarrow aaabbb$ — Why? Stop nesting with $S \to ε$ .

Verify: Count of a $= 3$ , count of b $= 3$ , they are equal, and all a's precede all b's (the rule can never interleave them). So the form is $a^{3} b^{3}$ with $n = 3$ . ✓

C3 — The degenerate case: the empty string

C4 — Two-sided / non-1:1 counts $a^{n} b^{2 n}$

C5 — Detecting ambiguity

Worked example Prove

$G_{5} : E \to E + E ∣ a$ is ambiguous using a+a+a Forecast: With three a's joined by +, can you group them as $(a + a) + a$ and $a + (a + a)$ ? If both derivations exist, the grammar is ambiguous.

Tree L (left group):

$E \Rightarrow E + E$ — split into a left sum and a right term.
$\Rightarrow E + E + E$ — Why? Expand the left $E$ into $E + E$ , making the grouping $(a + a) + a$ .
$\Rightarrow^{*} a + a + a$ — finish all $E \to a$ .

Tree R (right group):

$E \Rightarrow E + E$ .
$\Rightarrow E + E + E$ — Why? This time expand the right $E$ , making $a + (a + a)$ .
$\Rightarrow^{*} a + a + a$ .

These two are distinct parse trees (different parent–child structure at the root), shown side by side:

Verify: Both trees yield the same string a+a+a (5 symbols). They differ in structure (which + is at the root), so by definition the grammar has ≥2 parse trees for one string $\Rightarrow$ ambiguous. ✓

C6 — Removing ambiguity with precedence layers

Worked example Give

a+a*a a unique tree using $G_{3}$ $E \to E + T ∣ T, T \to T * F ∣ F, F \to a$ Forecast: Which operator will end up nearest the root (evaluated last)? Guess before deriving.

$E \Rightarrow E + T$ — Why? + is the lowest-precedence layer, so it must sit at the top; only the $E$ -level rule produces it.
$\Rightarrow T + T$ — Why? The left operand is just a term (no + inside), so $E \to T$ .
$\Rightarrow F + T$ then $\Rightarrow a + T$ — Why? That term is a bare factor a.
$\Rightarrow a + T * F$ — Why? The right operand a*a is a *-term, produced only at the $T$ layer, which forces it below the +.
$\Rightarrow^{*} a + a * a$ — finish with $T \to F$ , $F \to a$ .

Verify: There is exactly one parse tree — * is structurally forced under +, giving the grouping $a + (a * a)$ . Any attempt to make + bind tighter would need + inside a $T$ , but no $T$ -rule produces +. Unique tree ⇒ unambiguous for this string. ✓ (This is why Compilers — parsing uses layered grammars.)

C7 — Ordering vs structure (leftmost = rightmost = same tree)

Worked example Two derivations of

ab in $G_{7} : S \to A B, A \to a, B \to b$ — same tree? Forecast: One derivation expands $A$ first, another expands $B$ first. Different trees or not?

Leftmost: $S \Rightarrow A B \Rightarrow a B \Rightarrow ab$ (always rewrite the leftmost variable). Rightmost: $S \Rightarrow A B \Rightarrow A b \Rightarrow ab$ (always rewrite the rightmost variable).

Both start $S \Rightarrow A B$ — Why? Only one $S$ -rule exists.
They differ only in which of $A, B$ you replace first — Why does that not matter? $A$ and $B$ live in separate subtrees; expanding one never affects the other.

Verify: Draw the tree: root $S$ , children $A$ and $B$ , with leaves $a$ and $b$ . Both derivations produce this identical tree. So there are 2 derivations but 1 parse tree ⇒ this grammar is not ambiguous by these strings. Distinct-tree count $= 1$ . ✓

Recall Derivations vs trees, in one line

Leftmost derivation ↔ parse tree is a bijection. Count trees, never raw derivations, when testing ambiguity.

C8 — Word problem: nested if/else (real syntax)

Worked example Model statements

$\to$ show the "dangling else" is ambiguous Grammar $G_{8}$ (S = statement): $S \to if S ∣ if S else S ∣ x$ where $x$ is a plain statement. Forecast: In if if x else x, does the else attach to the inner if or the outer if? If both are legal, we have a real bug.

Attach to inner if:

$S \Rightarrow if S$ — Why? Outer if with no else (first rule).
$\Rightarrow if if S else S$ — Why? Inner statement is an if-else (second rule); the else belongs to the inner if.
$\Rightarrow^{*} if if x else x$ .

Attach to outer if:

$S \Rightarrow if S else S$ — Why? Outer if has the else (second rule).
$\Rightarrow if if x else x$ — inner is a bare if x, so the else binds to the outer.

Verify: Both derivations yield the identical token string if if x else x, yet the else sits in different subtrees ⇒ two parse trees ⇒ ambiguous. This is the famous dangling-else problem; real languages fix it with a rule "else binds to nearest unmatched if" — exactly a precedence-layer trick like Ex 6. ✓

C9 — Exam twist: a union of two count-conditions

Worked example Build a CFG for

$L = {a^{i} b^{j} c^{k} ∣ i = j or j = k}$ Forecast: Two separate conditions joined by "or". Guess: one start rule branching to two sub-grammars?

The or means union, so $S$ chooses one branch: $S \to S_{1} ∣ S_{2}, S_{1} \to A C, A \to a A b ∣ ε, C \to c C ∣ ε, S_{2} \to A^{'} B, A^{'} \to a A^{'} ∣ ε, B \to b B c ∣ ε .$ Branch $S_{1}$ forces $i = j$ (via $A \to a A b$ ) and lets $k$ be free (via $C$ ). Branch $S_{2}$ forces $j = k$ (via $B \to b B c$ ) and lets $i$ be free.

Test string aabbc ( $i = 2, j = 2, k = 1$ ; here $i = j$ holds).

$S \Rightarrow S_{1}$ — Why? Since $i = j$ , take the branch that enforces it.
$S_{1} \Rightarrow A C$ .
$A \Rightarrow a A b \Rightarrow aa A bb \Rightarrow aabb$ — Why? Two wraps give $a^{2} b^{2}$ , matching $i = j = 2$ .
$C \Rightarrow c C \Rightarrow c$ — Why? One c for $k = 1$ , free of any count constraint.
Assemble: $A C \Rightarrow^{*} aabb c =$ aabbc.

Verify: For aabbc: $i = 2, j = 2, k = 1$ . Condition $i = j$ : $2 = 2$ ✓ (so the string is in $L$ regardless of $k$ ). Counts check: two a, two b, one c, in order $a^{*} b^{*} c^{*}$ . ✓

Active Recall

Recall (C3) Why must you always check the

$ε$ / $n = 0$ case? Because $ε \in Σ^{*}$ is a real length-0 string; languages like $a^{n} b^{n}$ include it at $n = 0$ . Skipping it loses a valid member.

Recall (C5 vs C7) Two derivations exist — is the grammar ambiguous?

Only if they give two distinct parse trees (two distinct leftmost derivations). Two orderings of the same tree (Ex 7) prove nothing.

Recall (C9) Can one CFG force

$i = j$ AND $j = k$ at once for $a^{i} b^{j} c^{k}$ ? No — ${a^{n} b^{n} c^{n}}$ is not context-free (pumping lemma). You can do the union (or), not the intersection (and).

Recall (C6) In a precedence-layered grammar, which operator ends up nearest the root?

The lowest-precedence one (e.g. +), because only the top layer produces it, forcing higher-precedence ops into deeper subtrees.

Connections

Parent: 4.6.08 Context-free grammars (CFG) — productions, derivations, parse trees (Hinglish)
Regular expressions and DFAs · Pushdown automata · Chomsky hierarchy
Chomsky normal form · Pumping lemma for CFLs · Compilers — parsing