Chomsky Normal Form (CNF) — conversion: Exercises

Throughout, the vocabulary is the one built in the parent note. A quick refresher of the two symbols you must never confuse:

Definition The augmented start symbol

$S_{0}$ (so the notation is earned) Several problems below (and the CNF definition itself) use a symbol written $S_{0}$ . It is the augmented start symbol: a brand-new variable we add at the very start of conversion via the single rule $S_{0} \to S$ , where $S$ was the grammar's original start symbol. Picture it as a fresh "front door" box that only points to the old start box. Why add it? CNF allows the start symbol — and only the start symbol — to have the rule $\to ε$ . If the original $S$ appears on the right-hand side of some rule, giving it an $ε$ -rule tangles that occurrence. By promoting a fresh $S_{0}$ that never appears on any right-hand side, the start stays "clean" and the special $S_{0} \to ε$ exception can be handled safely. From here on, " $S_{0}$ " always means this augmented start.

Level 1 — Recognition

Exercise 1.1

For each rule, say CNF-legal or not, and if not, name the exact violation: (a) $A \to B C$ (b) $A \to a$ (c) $A \to a B$ (d) $A \to B$ (e) $A \to B C D$ (f) $A \to ε$ (where $A$ is not the start symbol) (g) $S_{0} \to ε$ (where $S_{0}$ is the start symbol).

Recall Solution 1.1

Recall the two allowed shapes: box→two boxes, or box→one tile (plus start→ε).

(a) Legal — $A \to B C$ is exactly two variables. ✓
(b) Legal — one terminal. ✓
(c) Illegal — mixed terminal and variable. A single rule may not contain both a tile and a box.
(d) Illegal — unit rule (a rename); it produces neither a tile nor a branch into two boxes.
(e) Illegal — too long (three variables). CNF caps the right side at two.
(f) Illegal — an $ε$ -rule on a non-start variable is forbidden.
(g) Legal — only the start symbol is allowed to vanish, and only this way. ✓

Exercise 1.2

The grammar $G : S \to A B, A \to a, B \to b$ — is it already in CNF? Justify rule-by-rule.

Recall Solution 1.2

$S \to A B$ : two variables → shape $A \to B C$ . ✓
$A \to a$ : one terminal → shape $A \to a$ . ✓
$B \to b$ : one terminal. ✓

Every rule matches a permitted shape, so yes, $G$ is already in CNF. No conversion needed.

Level 2 — Application (single steps)

Exercise 2.1 (DEL — nullable set)

Grammar: $S \to A B, A \to a A ∣ ε, B \to b B ∣ ε$ . Compute the nullable set $N$ by fixed-point iteration.

Recall Solution 2.1

A variable is nullable if it can derive the empty string. Build $N$ from scratch:

Round 1 (direct $ε$ -rules): $A \to ε$ so $A \in N$ ; $B \to ε$ so $B \in N$ . Now $N = {A, B}$ .
Round 2 (all-nullable right sides): $S \to A B$ — both $A, B \in N$ , so $S \in N$ . Now $N = {A, B, S}$ .
Round 3: nothing new appears → fixed point reached.

$N = {S, A, B} .$

Exercise 2.2 (DEL — patching a rule)

Given $N = {X, Z}$ (so $X, Z$ nullable, $Y$ not), list the rules DEL produces from $A \to X Y Z$ .

Recall Solution 2.2

The nullable positions are ${X, Z}$ . Add a version for every subset of those positions dropped, but never delete everything down to empty:

drop nothing: $A \to X Y Z$
drop $X$ : $A \to Y Z$
drop $Z$ : $A \to X Y$
drop $X$ and $Z$ : $A \to Y$

$A \to X Y Z ∣ Y Z ∣ X Y ∣ Y .$ With two nullable positions there are $2^{2} = 4$ subsets, and none collapses to empty (because $Y$ stays), so all four survive.

Exercise 2.3 (UNIT — unit pairs)

Grammar: $A \to B, B \to C, C \to c$ . List all unit pairs $(X, Y)$ with $X \Rightarrow^{*} Y$ by unit rules only, then give the grammar after UNIT.

Recall Solution 2.3

A unit pair $(X, Y)$ means $X$ reaches $Y$ using only rename rules (reflexive: every variable reaches itself). The unit rules are $A \to B, B \to C$ .

Reflexive: $(A, A), (B, B), (C, C)$ .
Direct: $(A, B), (B, C)$ .
Transitive: $A \to B \to C$ gives $(A, C)$ .

Full set: $(A, A), (A, B), (A, C), (B, B), (B, C), (C, C)$ .

Now for each variable, copy the non-unit bodies of everything it reaches. The only non-unit rule is $C \to c$ .

$A$ reaches $C$ → gets $A \to c$ .
$B$ reaches $C$ → gets $B \to c$ .
$C \to c$ stays.

After UNIT (rename rules dropped): $A \to c, B \to c, C \to c .$

Exercise 2.4 (TERM)

Apply TERM to $A \to a B b$ .

Recall Solution 2.4

TERM isolates terminals that sit inside a rule alongside variables. Here $a$ and $b$ are mixed with $B$ . Introduce a fresh box per distinct terminal: $T_{a} \to a, T_{b} \to b,$ then replace the terminals in the body: $A \to T_{a} B T_{b} .$ Now the long rule contains only variables (length still 3 — BIN will handle that next).

Exercise 2.5 (BIN)

Apply BIN to $A \to B C D E$ (four variables). How many helper variables appear?

Recall Solution 2.5

BIN chops a long right side into a chain of length-2 rules, each holding "the rest": $A \to B X_{1}, X_{1} \to C X_{2}, X_{2} \to D E .$ A right side of length $k$ needs $k - 2$ helpers. Here $k = 4$ , so $4 - 2 = 2$ helpers ( $X_{1}, X_{2}$ ).

Level 3 — Analysis (multi-step reasoning)

Exercise 3.1

Grammar: $S \to 0 S 0 ∣ 1 S 1 ∣ ε$ . Convert fully to CNF (Sipser order START → DEL → UNIT → TERM → BIN). Note $ε$ is in the language.

Recall Solution 3.1

START. Add $S_{0} \to S$ . Rules: $S_{0} \to S$ ; $S \to 0 S 0 ∣ 1 S 1 ∣ ε$ .

DEL. Nullable: $S \to ε$ gives $S \in N$ . Is $S_{0}$ nullable? $S_{0} \to S$ with $S$ nullable → yes, $S_{0} \in N$ . So $N = {S, S_{0}}$ . Patch rules over nullable positions:

$S \to 0 S 0$ : nullable position is the middle $S$ . Drop it → add $S \to 00$ . Body $0 S 0 ∣ 00$ .
$S \to 1 S 1$ : similarly → $S \to 11$ . Body $1 S 1 ∣ 11$ .
$S \to ε$ : delete (S is not the start).
$S_{0} \to S$ : $S$ nullable, but dropping it would give $S_{0} \to ε$ — keep that one, because $ε$ is in the language and $S_{0}$ is the start. So keep $S_{0} \to ε$ and $S_{0} \to S$ .

After DEL: $S_{0} \to S ∣ ε$ ; $S \to 0 S 0 ∣ 00 ∣ 1 S 1 ∣ 11$ .

UNIT. Unit pairs: $(S_{0}, S_{0}), (S_{0}, S), (S, S)$ . The only rename is $S_{0} \to S$ . Copy $S$ 's non-unit bodies into $S_{0}$ : $S_{0} \to 0 S 0 ∣ 00 ∣ 1 S 1 ∣ 11 ∣ ε, S \to 0 S 0 ∣ 00 ∣ 1 S 1 ∣ 11.$

TERM. Terminals $0, 1$ appear mixed. Add $T_{0} \to 0, T_{1} \to 1$ : $S_{0} \to T_{0} S T_{0} ∣ T_{0} T_{0} ∣ T_{1} S T_{1} ∣ T_{1} T_{1} ∣ ε,$ $S \to T_{0} S T_{0} ∣ T_{0} T_{0} ∣ T_{1} S T_{1} ∣ T_{1} T_{1} .$

BIN. The length-3 rules $T_{0} S T_{0}$ and $T_{1} S T_{1}$ need one helper each: $T_{0} S T_{0} \to T_{0} C_{0}, C_{0} \to S T_{0},$ $T_{1} S T_{1} \to T_{1} C_{1}, C_{1} \to S T_{1} .$ Final CNF:

S_{0} S C_{0} \to T_{0} C_{0} ∣ T_{0} T_{0} ∣ T_{1} C_{1} ∣ T_{1} T_{1} ∣ ε \to T_{0} C_{0} ∣ T_{0} T_{0} ∣ T_{1} C_{1} ∣ T_{1} T_{1} \to S T_{0}, C_{1} \to S T_{1}, T_{0} \to 0, T_{1} \to 1

The language is even-length binary palindromes (including $ε$ ), unchanged. ✓

Exercise 3.2

For the final grammar of Exercise 3.1, draw the CNF parse tree of the string $0110$ and count its nodes. Verify the count matches the CNF prediction $2 n - 1$ .

Recall Solution 3.2

$0110$ has length $n = 4$ . The outer letters are $0 \dots 0$ , so start with the $0$ -rule; the inner block $11$ comes from the $1$ -rule: $S_{0} \Rightarrow T_{0} C_{0} \Rightarrow T_{0} (S T_{0}) \Rightarrow T_{0} ((T_{1} T_{1}) T_{0}) \Rightarrow 011 0.$ Reading the figure. The diagram draws this exact tree, top to bottom. The blue nodes ( $S_{0}$ , $C_{0}$ , $S$ ) are the branching nodes — trace each one and you will see it splits into exactly two children (drawn as two blue edges), which is the visual signature of CNF: a binary tree. The orange nodes ( $T_{0}, T_{1}$ ) are terminal-helper boxes, each sending a single green edge down to a finished tile ( $0$ or $1$ ) at the bottom row. Follow the bottom row left-to-right and you read off the string $0, 1, 1, 0$ .

Now count using the tree's structure. In a binary parse tree for a length- $n$ string: $branching nodes = n - 1, leaf tiles = n, total structural nodes = 2 n - 1.$ Here $n = 4$ : branching nodes $= 3$ (the three blue nodes $S_{0}, C_{0}, S$ ), leaf tiles $= 4$ (the four bottom green tiles), total $= 2 (4) - 1 = 7$ . The figure's node count matches. That fixed, predictable size is exactly why CYK runs in $O (n^{3})$ .

Exercise 3.3

Convert $S \to A a B, A \to ε, B \to b B ∣ ε$ to CNF. Watch the ordering carefully.

Recall Solution 3.3

START. $S_{0} \to S$ . Rules: $S_{0} \to S$ ; $S \to A a B$ ; $A \to ε$ ; $B \to b B ∣ ε$ .

DEL. Nullable: $A \to ε \Rightarrow A$ ; $B \to ε \Rightarrow B$ . $S \to A a B$ contains terminal $a$ (not nullable) so $S \in / N$ . $S_{0} \to S$ , $S$ not nullable → $S_{0} \in / N$ . So $N = {A, B}$ . Patch $S \to A a B$ (nullable positions $A$ and $B$ ; the tile $a$ always stays):

keep both: $A a B$
drop $A$ : $a B$
drop $B$ : $A a$
drop both: $a$

$S \to A a B ∣ a B ∣ A a ∣ a$ . Delete $A \to ε$ and $B \to ε$ ; $B \to b B$ patches to $B \to b B ∣ b$ . After DEL: $S_{0} \to S$ ; $S \to A a B ∣ a B ∣ A a ∣ a$ ; $B \to b B ∣ b$ .

PRUNE (remove non-generating symbols). A variable is generating if it can eventually derive a string of terminals only. After deleting $A \to ε$ , the variable $A$ has no productions at all, so it can generate nothing — it is non-generating. Any rule body that contains $A$ (here $A a B$ and $A a$ ) can therefore never finish deriving into terminals, so those bodies are dead and are removed. Why this preserves the language: a dead body contributes zero terminal strings, so deleting it removes no derivable string — the language is unchanged. Remove $A$ and its dead bodies: $S_{0} \to S; S \to a B ∣ a; B \to b B ∣ b .$

UNIT. Pairs: $(S_{0}, S)$ . Copy $S$ 's non-unit bodies to $S_{0}$ : $S_{0} \to a B ∣ a$ . Drop $S_{0} \to S$ . $S_{0} \to a B ∣ a; S \to a B ∣ a; B \to b B ∣ b .$

TERM. $T_{a} \to a, T_{b} \to b$ . Bodies $a B \to T_{a} B$ , $b B \to T_{b} B$ : $S_{0} \to T_{a} B ∣ a, S \to T_{a} B ∣ a, B \to T_{b} B ∣ b, T_{a} \to a, T_{b} \to b .$

BIN. All right sides now have length ≤ 2 — nothing to chop.

Final CNF: $S_{0} \to T_{a} B ∣ a, S \to T_{a} B ∣ a, B \to T_{b} B ∣ b, T_{a} \to a, T_{b} \to b .$ Language $= {a b^{n} : n \geq 0} = {a, ab, abb, \dots}$ . ✓

Level 4 — Synthesis (build to spec)

Exercise 4.1

Design a CNF grammar for $L = {a^{n} b^{n} : n \geq 1}$ directly (not by converting), then confirm it derives $aabb$ .

Recall Solution 4.1

We want each $a$ matched by a later $b$ . Structure: an outer $a \dots b$ wrapping a smaller copy. In CNF we need boxes only: $S \to A C, C \to S B, S \to A B, A \to a, B \to b .$ Reading it: $S \to A C$ places one $a$ (via $A$ ) then $C = S B$ = (inner matched string)(one $b$ ). Base case $S \to A B$ = single $ab$ . Derive $aabb$ : $S \Rightarrow A C \Rightarrow A (S B) \Rightarrow A (A B) B \Rightarrow aabb .$ Every rule is $A \to B C$ or $A \to a$ → valid CNF, and $L (G) = {a^{n} b^{n} : n \geq 1}$ . ✓

Exercise 4.2

Build a CNF grammar whose language is ${w \in {a, b}^{*} : ∣ w ∣ is exactly 2}$ (all length-2 strings over ${a, b}$ ). How many right sides does $S$ need?

Recall Solution 4.2

Length-2 strings: $aa, ab, ba, bb$ — four of them. In CNF the top rule must produce two boxes, each a single letter: $S \to AA ∣ A B ∣ B A ∣ B B, A \to a, B \to b .$ $S$ needs $4$ right sides (one per ordered pair of letters). Each expands to a length-2 tile pair — exactly the strings of length 2. ✓ (This is finite, so $ε \in / L$ and no start- $ε$ rule is needed.)

Exercise 4.3

Convert $S \to S S ∣ (S) ∣ ε$ (balanced parentheses, treating ( and ) as terminals, including the empty string) to CNF.

Recall Solution 4.3

Write terminals as $ℓ$ = ( and $r$ = ). START. $S_{0} \to S$ ; $S \to S S ∣ ℓ S r ∣ ε$ . DEL. Nullable: $S \to ε \Rightarrow S \in N$ ; $S_{0} \to S \Rightarrow S_{0} \in N$ . $N = {S, S_{0}}$ . Patch:

$S \to S S$ : both positions nullable. Subsets: keep both $S S$ ; drop one $S$ (either) → $S$ ; drop both → $ε$ (deleted). So add $S \to S$ (a unit! handled next) and keep $S S$ .
$S \to ℓ S r$ : middle $S$ nullable → drop it: $ℓ r$ . Body $ℓ S r ∣ ℓ r$ .
Delete $S \to ε$ ; keep $S_{0} \to ε$ (since $ε \in L$ ).

After DEL: $S_{0} \to S ∣ ε$ ; $S \to S S ∣ S ∣ ℓ S r ∣ ℓ r$ . UNIT. Unit rules: $S_{0} \to S$ , and $S \to S$ (trivial self-loop, remove). Pairs: $(S_{0}, S)$ . Non-unit bodies of $S$ : ${S S, ℓ S r, ℓ r}$ . Copy to $S_{0}$ : $S_{0} \to S S ∣ ℓ S r ∣ ℓ r ∣ ε, S \to S S ∣ ℓ S r ∣ ℓ r .$ TERM. $L \to ℓ$ ((), $R \to r$ ()). Rewrite $ℓ S r \to L S R$ and $ℓ r \to L R$ : $S_{0} \to S S ∣ L S R ∣ L R ∣ ε, S \to S S ∣ L S R ∣ L R .$ BIN. Length-3 rule $L S R$ needs one helper: $L S R \to L M$ , $M \to S R$ . Final CNF:

S_{0} S M \to S S ∣ L M ∣ L R ∣ ε \to S S ∣ L M ∣ L R \to S R, L \to (, R \to)

( $L \to$ ( and $R \to$ ).) Balanced parentheses, including $ε$ , unchanged. ✓

Level 5 — Mastery (subtle & complete)

Exercise 5.1

Ordering counterexample. Take $S \to A b, A \to ε$ . Show that doing BIN/TERM first, then DEL can leave a stray rule that violates CNF, whereas Sipser's order does not. Explain precisely.

Recall Solution 5.1

Sipser order (correct). After START: $S_{0} \to S$ ; $S \to A b$ ; $A \to ε$ . DEL: $A$ nullable, $N = {A}$ . $S \to A b$ → drop $A$ : $S \to b$ ; keep $S \to A b$ . But $A$ now has no rules (dead) → prune $A b$ . Left $S \to b$ ; $S_{0} \to S$ . UNIT: $(S_{0}, S)$ → $S_{0} \to b$ . Result $S_{0} \to b$ ; $S \to b$ . TERM/BIN: nothing needed (single terminal is legal). Clean CNF. ✓

Wrong order (TERM/BIN before DEL). TERM on $S \to A b$ : add $T_{b} \to b$ , get $S \to A T_{b}$ . BIN: length 2, fine. Now DEL: $A$ nullable, patch $S \to A T_{b}$ → drop $A$ : $S \to T_{b}$ . That is a unit rule $S \to T_{b}$ ! It was created after the UNIT step would have run, so if you already ran UNIT, nothing removes it — CNF violated. You'd have to re-run UNIT.

Precise reason: TERM turns the harmless terminal $b$ into a variable $T_{b}$ ; then DEL's dropping of the nullable $A$ leaves the single variable $T_{b}$ , i.e. a rename. Doing DEL first means $b$ is still a terminal when it's dropped-to, giving legal $S \to b$ , not a unit. Sipser's DEL-before-TERM avoids the cleanup loop.

Exercise 5.2

Full pipeline, everything at once. Convert $S \to A S A ∣ a B, A \to B ∣ S, B \to b ∣ ε .$ (This is the parent note's Example 1 — reproduce the final CNF and independently verify $L$ contains the string $b$ .)

Recall Solution 5.2

Following the parent note's full run (START, DEL with $N = {A, B}$ , UNIT with pairs $(S_{0}, S), (A, S), (A, B)$ , TERM on $a B$ , BIN on $A S A$ ) the final grammar is:

S_{0}, S A A_{1} \to A A_{1} ∣ S A ∣ A S ∣ T_{a} B ∣ a \to A A_{1} ∣ S A ∣ A S ∣ T_{a} B ∣ a ∣ b \to S A, B \to b, T_{a} \to a

Check $b \in L$ ? Trace $b$ : is there a start derivation of the single tile $b$ ? $S_{0}$ 's bodies are $A A_{1}, S A, A S, T_{a} B, a$ — none is a single $b$ directly. $S_{0} \to T_{a} B \Rightarrow a b$ ? That gives $ab$ , not $b$ . Try $S_{0} \to a$ → gives $a$ . There is no $S_{0}$ rule producing exactly $b$ , and every branching body forces at least two symbols or an $a$ . So $b \in / L (G)$ . Sanity against the original grammar: can $S$ derive $b$ ? $S \to a B \Rightarrow ab$ , $S \to A S A$ — $A$ can be $ε$ (nullable) giving $S \Rightarrow S$ ; you always keep at least the productive core. The shortest strings are $a$ and $ab$ ; $b$ alone is not derivable from $S$ . Both grammars agree: $b \in / L$ . ✓ (This is a negative verification — a good habit.)

Exercise 5.3

Node-count mastery. In any CNF grammar, a derivation of a string of length $n \geq 1$ uses exactly how many rule applications of type $A \to B C$ , and how many of type $A \to a$ ? Prove the totals.

Recall Solution 5.3

Let $n \geq 1$ be the string length.

Type $A \to a$ (terminal rules): each produces exactly one final tile, and every tile is produced by exactly one such rule. So there are exactly $n$ of them.
Type $A \to B C$ (branching rules): think of the binary parse tree. It has $n$ leaves (the tiles). A full binary tree with $n$ leaves has exactly $n - 1$ internal branching nodes. Each branching node corres