Chapter 19 of 34

Simplification of CFGs

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 changes

Worked example

S → aA | bB | a
A → aA | b
B → bB
C → cS | d
D → Aa | B

Step 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 → Aa

Step 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 | b

The 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 → bB
  • Correct 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 changes

Building 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 → d

Nullable 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 → d

Notice 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 changes

This 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 ) | a

Unit 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 ) | a

Same 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 → eA

Step 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 | e

Step 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 | e

Step 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 | e

Step 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 | d

Both 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.