Grammars written by hand, or produced by some conversion algorithm, are often messy. Some variables can never produce a string. Some can never be reached from the start symbol. Some productions only rename one variable into another (A → B), and some produce nothing at all (A → ε).
None of these change the language much, but they make grammars longer, harder to reason about, and unsuitable for algorithms such as parsing and the normal-form conversions in the next chapters. So we clean them up.
Simplifying a CFG means transforming it into an equivalent grammar (same language, except possibly for ε) that has no useless symbols, no ε-productions and no unit productions.
In this chapter we will learn the three cleaning algorithms, why they must be applied in a specific order, and work through complete exam-style examples. Every result below was produced by a program implementing the algorithms, and the cleaned grammars were checked against the originals on all strings up to length 7 or 8.
The Three Kinds of Junk
Junk | Form | Why it is a problem |
|---|---|---|
Useless symbol | a variable that never helps derive a terminal string | dead weight; confuses analysis |
ε-production | A → ε | sentential forms can shrink, so derivation length is not tied to string length |
Unit production | A → B (one variable alone) | steps that produce nothing; can form cycles A → B → A |
We will remove them in the order ε-productions, then unit productions, then useless symbols. The reason for this order is explained after we see each algorithm. We start with useless symbols because they are the simplest idea.
1. Removing Useless Symbols
A symbol X is useful if there is a derivation S ⇒* αXβ ⇒* w for some terminal string w. Otherwise X is useless.
Being useful needs two things:
Generating: X ⇒* w for some terminal string w (X can finish).
Reachable: S ⇒* αXβ for some α, β (X can appear).
Finding generating symbols
GEN = all terminals
repeat
if A → X1 X2 ... Xk and every Xi is in GEN, add A to GEN
until nothing changes(A → ε counts too: the empty body has nothing outside GEN.)
Finding reachable symbols
REACH = { S }
repeat
if A is in REACH and A → α, add every symbol of α to REACH
until nothing changesWorked example
S → aA | bB | a
A → aA | b
B → bB
C → cS | d
D → Aa | BStep 1: generating variables.
Round 1: S (S → a), A (A → b), C (C → d) have an all-terminal body.
Round 2: D (D → Aa, and A is generating).
Round 3: nothing new. B only has B → bB, which always leaves a B behind, so B can never finish.
Remove B and every production that mentions B (S → bB and D → B):
S → aA | a
A → aA | b
C → cS | d
D → AaStep 2: reachable symbols. From S we reach a and A; from A we reach a and b. C and D are never reached. Remove them:
S → aA | a
A → aA | bThe language is unchanged: { a } ∪ { anb | n ≥ 1 }, that is, a, ab, aab, aaab, …
Order matters: generating first, then reachable
S → AB | a
A → b
B → bBCorrect order. Generating: S, A (B is not). Remove B: S → a, A → b. Reachable: only S. Result: S → a.
Wrong order. Reachable first: S, A, B are all reachable (via S → AB). Then generating removes B and S → AB, leaving S → a, A → b. Now A is useless but still present.
Removing non-generating symbols can make other symbols unreachable, but removing unreachable symbols never makes a symbol non-generating. So: non-generating first, unreachable second.
2. Removing ε-Productions
The key concept is a nullable variable.
A variable A is nullable if A ⇒* ε.
Finding nullable variables
NULLABLE = { A | A → ε is a production }
repeat
if A → B1 B2 ... Bk and every Bi is in NULLABLE, add A
until nothing changesBuilding the new productions
For every production A → X1…Xk, add every version obtained by keeping or deleting each nullable occurrence. If the body has m nullable occurrences, that gives up to 2m versions. Then:
delete all ε-productions, and
do not add a version whose body became empty.
The new grammar G' satisfies L(G') = L(G) − {ε}. If ε ∈ L(G) (that is, S is nullable) and you need ε back, add a new start symbol S' → S | ε.
Why it works: any time the old grammar used a variable only to erase it, the new grammar simply never writes that variable in the first place.
Worked example
S → ABaC
A → BC
B → b | ε
C → D | ε
D → dNullable variables. B and C directly (B → ε, C → ε). Then A, because A → BC and both are nullable. S is not nullable (its body contains the terminal a). D is not nullable.
New productions. S → ABaC has three nullable occurrences (A, B, C), so 23 = 8 versions:
Keep A? | Keep B? | Keep C? | Body |
|---|---|---|---|
yes | yes | yes | ABaC |
yes | yes | no | ABa |
yes | no | yes | AaC |
yes | no | no | Aa |
no | yes | yes | BaC |
no | yes | no | Ba |
no | no | yes | aC |
no | no | no | a |
A → BC gives BC, B, C (the fourth version, ε, is dropped). The result:
S → ABaC | ABa | AaC | Aa | BaC | Ba | aC | a
A → BC | B | C
B → b
C → D
D → dNotice that ε-removal created new unit productions A → B and A → C. That is exactly why units are removed after ε-productions.
A small example with a nullable start symbol
S → aSb | SS | εS is nullable. S → aSb gives aSb and ab; S → SS gives SS and S (drop the useless S → S). Result: S → aSb | ab | SS, which generates every non-empty string of the original language. To keep ε, add S' → S | ε.
3. Removing Unit Productions
A unit production has the form A → B where A and B are both variables.
A → a (single terminal) is not a unit production.
Unit pairs
(A, B) is a unit pair if A ⇒* B using only unit productions. Compute them as follows:
PAIRS = { (A, A) | A is a variable }
repeat
if (A, B) is in PAIRS and B → C is a unit production, add (A, C)
until nothing changesThis handles chains (A → B → C) and cycles (A → B → A) without looping forever.
Building the new productions
For every unit pair (A, B) and every non-unit production B → α, add A → α. Then delete all unit productions.
Worked example: the expression grammar
E → E + T | T
T → T * F | F
F → ( E ) | aUnit productions: E → T and T → F. Unit pairs:
Pair | Why | Non-unit bodies copied to the left variable |
|---|---|---|
(E, E) | trivial | E + T |
(E, T) | E → T | T * F |
(E, F) | E → T → F | ( E ), a |
(T, T) | trivial | T * F |
(T, F) | T → F | ( E ), a |
(F, F) | trivial | ( E ), a |
Result:
E → E + T | T * F | ( E ) | a
T → T * F | ( E ) | a
F → ( E ) | aSame language (checked on all 60 strings of length ≤ 7 in the language), no unit productions. Derivations are shorter: a now takes one step from E instead of three.
The Correct Order and Why
Apply the steps in this order: (1) remove ε-productions, (2) remove unit productions, (3) remove useless symbols (non-generating first, then unreachable).
Step | Can it create… | Consequence |
|---|---|---|
ε-removal | new unit productions (A → BC with C nullable gives A → B) | so unit removal must come after it |
unit removal | unreachable symbols (a variable used only via A → B may no longer be mentioned) | so useless removal must come after it |
unit removal | new ε-productions? No (it copies only non-unit bodies, and none of them is ε any more) | safe |
useless removal | new ε or unit productions? No (it only deletes) | safe to do last |
Complete Worked Example
Simplify:
S → AB | Ca
A → aA | ε
B → bB | b | D
C → Cc
D → d
E → eAStep 1: remove ε-productions
Nullable: A only (A → ε). B is not nullable (every B-body contains a terminal or D, and D is not nullable). S → AB is not nullable because B is not.
S → AB gives AB and B.
A → aA gives aA and a.
E → eA gives eA and e.
S → AB | B | Ca
A → aA | a
B → bB | b | D
C → Cc
D → d
E → eA | eStep 2: remove unit productions
Unit productions: S → B and B → D. Non-trivial unit pairs: (S, B), (S, D) via S → B → D, and (B, D).
(S, B) copies bB, b to S.
(S, D) copies d to S.
(B, D) copies d to B.
S → AB | Ca | bB | b | d
A → aA | a
B → bB | b | d
C → Cc
D → d
E → eA | eStep 3a: remove non-generating symbols
Generating: A (a), B (b), D (d), E (e), and S (b). C only has C → Cc, so it never finishes: C is non-generating. Remove C and S → Ca:
S → AB | bB | b | d
A → aA | a
B → bB | b | d
D → d
E → eA | eStep 3b: remove unreachable symbols
From S: A, B, a, b, d. From A and B: nothing new. D is no longer reachable (it was reachable only through B → D, which unit removal deleted), and E was never reachable.
S → AB | bB | b | d
A → aA | a
B → bB | b | dBoth grammars generate a*b*(b + d): any number of a's, then any number of b's, ending with b or d. (Verified by program on every string up to length 8.)
Size of the Result
Useless-symbol removal only deletes, so the grammar can only shrink.
Unit removal can increase the number of productions: each variable receives the non-unit bodies of every variable it unit-reaches.
ε-removal can blow up a production with m nullable occurrences into as many as 2m productions (2m − 1 when every symbol of the body is nullable, because the empty version is dropped). (If bodies are first broken into pieces of length 2, as in the next chapter, the blow-up stays small.)
Common Mistakes
Wrong order inside useless-symbol removal. Unreachable first and then non-generating can leave useless symbols behind.
Forgetting indirect nullability. A → BC is nullable if both B and C are nullable, even though A has no ε-production of its own.
Dropping only one occurrence. In A → BaB with B nullable, you need BaB, aB, Ba and a, not just aB and Ba.
Adding an empty body. When every symbol of a body is nullable, the all-deleted version is ε; do not add it.
Silently losing ε. After ε-removal the new grammar never generates ε. If the original did, say so (L(G') = L(G) − {ε}) or add a new start S' → S | ε.
Treating A → a as a unit production. Only variable-to-single-variable productions are unit productions.
Copying unit bodies during unit removal. Only non-unit bodies are copied; otherwise the unit productions come back.
GATE and Interview Questions
Q1. In S → ABC, A → a | ε, B → b | ε, C → c | ε, how many S-productions remain after removing ε-productions?
A, B and C are all nullable, so S → ABC has 23 = 8 versions. Dropping the empty one leaves 7: ABC, AB, AC, BC, A, B, C. Note that S itself is nullable, so the original language contains ε and the new grammar does not.
Q2. Find the useless symbols in S → AB | a, A → a, B → BC, C → b.
B is non-generating (B → BC never removes B). Removing B kills S → AB. Then A and C are unreachable. Useless: A, B, C. Result: S → a.
Q3. Why is ε-elimination done before unit-production elimination?
Because ε-elimination can create new unit productions. For example A → BC with C nullable produces A → B. If units were removed first, these new ones would survive.
Q4. What are the unit pairs of A → B | a, B → C | b, C → A | c?
The unit productions form the cycle A → B → C → A, so every variable unit-reaches every other: all nine pairs (X, Y) with X, Y ∈ {A, B, C}. After removal: A → a | b | c, B → a | b | c, C → a | b | c.
Q5. A variable is reachable and generating. Can it still be useless?
Yes, in principle. X might be reachable only inside a sentential form that also contains a non-generating variable, e.g. S → XB with B non-generating. That is exactly why we first delete non-generating symbols (and the productions using them), and only then compute reachability. After that, reachable and generating together do imply useful.
Q6. Does simplification change the language?
Removing useless symbols and unit productions never changes it. Removing ε-productions changes it only by removing ε (if ε was in the language).
Summary
Useless symbols are non-generating or unreachable. Remove non-generating first, then unreachable.
ε-productions: find nullable variables by fixed-point iteration, then add every version of each body with nullable symbols kept or dropped, never adding an empty body. The language loses only ε.
Unit productions: compute unit pairs, copy non-unit bodies along each pair, delete the units. Cycles are handled automatically.
Correct overall order: ε → unit → useless, because each step may create work only for the steps after it.
The cleaned grammar is the starting point for Chomsky Normal Form (next chapter) and Greibach Normal Form.
Clean grammars first: no dead variables, no empty rules, no pure renaming. Every later algorithm becomes simpler.