Simplification of CFG: Remove Epsilon, Unit and Useless Productions Step by Step

A CFG can look smaller after one deletion and still generate the wrong language. In S -> ABA, the nullable symbol A occurs twice, so epsilon removal needs four independent omission variants. Simplification of CFG: Eliminate Epsilon, Unit and Useless Productions Step by Step establishes the earlier one-occurrence pattern; this nine-nonterminal grammar adds repeated nullable positions, two transitive unit chains and a symbol audit that leaves six nonterminals.

1. What simplification of a CFG must preserve

CFG simplification preserves the language while removing avoidable epsilon productions, unit productions and useless symbols. It neither deletes every repetitive-looking rule nor requires a unique minimum grammar.

Keep these tests separate:

• A -> epsilon is an epsilon production.

• A -> B is a unit production because both sides are single nonterminals.

• A -> aB is neither an epsilon production nor a unit production.

• A non-generating symbol cannot derive a terminal-only string. An unreachable symbol is never reached from the start symbol.

If the language contains epsilon, a fresh start symbol may be needed to preserve it. Use this order: epsilon removal, unit removal, then useless-symbol removal. The first step can create unit rules, and the second can make symbols unreachable. This is not CNF or GNF conversion.

2. One grammar from start to finish

Let S be the start symbol. The nonterminals are {S, A, B, C, D, E, F, G, H}, and the terminals are {a, b, c, d, g, h}.

S -> ABA | aC | F
A -> aA | epsilon
B -> bB | C
C -> c | D
D -> E
E -> d
F -> FG | G
G -> g
H -> hH

A is nullable and appears twice in S -> ABA. Epsilon removal will create S -> B. Together with S -> F, B -> C, C -> D, D -> E and F -> G, that creates two transitive unit chains from S. H has no terminal base case. Later, D and E still generate terminal strings but become unreachable.

Three useful witnesses are:

• ada: S => ABA => aBA => aCA => aDA => aEA => adA => ada

• bd: S => ABA => BA => B => bB => bC => bD => bE => bd, using A => epsilon twice

• gg: S => F => FG => GG => gg

3. Step 1: remove the epsilon production

Only A is nullable, so NULLABLE = {A}. The start symbol is not nullable because B cannot vanish inside ABA, aC begins with terminal a, and F cannot derive epsilon.

Treat the two occurrences independently. From S -> ABA, keep both occurrences, omit the left one, omit the right one, or omit both. The result is ABA, BA, AB, B. Rule A -> aA also contributes A -> a. Now delete A -> epsilon.

S -> ABA | BA | AB | B | aC | F
A -> aA | a
B -> bB | C
C -> c | D
D -> E
E -> d
F -> FG | G
G -> g
H -> hH

These four variants preserve the cases in which the left A, the right A, both, or neither vanished in the old grammar.

4. Step 2: collapse every unit chain

Unit elimination uses closure. For X -> Y, follow the entire unit chain, copy each reachable non-unit production into X, then remove all unit rules.

The important closures are:

• U(S) = {S, B, C, D, E, F, G}

• U(B) = {B, C, D, E}

• U(C) = {C, D, E}

• U(D) = {D, E}

• U(F) = {F, G}

Through S -> B -> C -> D -> E, S inherits bB, c and d. Through S -> F -> G, it inherits FG and g. The non-unit alternatives ABA, BA, AB and aC stay unchanged. Applying the same closure method everywhere gives:

S -> ABA | BA | AB | aC | bB | c | d | FG | g
A -> aA | a
B -> bB | c | d
C -> c | d
D -> d
E -> d
F -> FG | g
G -> g
H -> hH

Keeping S -> B would leave a unit rule. Copying only B -> bB would also be incomplete because the transitive chain contributes c and d.

5. Step 3: remove non-generating and unreachable symbols

First mark generating symbols. In the epsilon-free grammar, the direct terminal bases give {A, C, E, G}. On the next closure step, B generates through C, D through E, F through G, and S through aC, so the set becomes {S, A, B, C, D, E, F, G}. H never enters it because H -> hH has no terminating alternative. Remove H.

Now compute reachability on the unit-free grammar. Start with R0 = {S}. The right-hand sides of the S productions add {A, B, C, F, G}, and no later pass adds anything. Therefore D and E are generating but unreachable, so remove them.

The final grammar is:

S -> ABA | BA | AB | aC | bB | c | d | FG | g
A -> aA | a
B -> bB | c | d
C -> c | d
F -> FG | g
G -> g

It has no epsilon production, no right-hand side consisting of one nonterminal, and no non-generating or unreachable symbol.

6. Language checks and traps that lose marks

The three witnesses still have derivations:

• ada: S => ABA => aBA => adA => ada

• bd: S => bB => bd

• gg: S => FG => gG => gg

The final grammar generates exactly {a^i b^j x a^k | i, j, k >= 0 and x in {c, d}} union {g^n | n >= 1}. Alternatives ABA, BA, AB, bB, c and d cover the boundary cases for the leading and trailing a-runs; aC duplicates the case i = 1, j = k = 0. Alternatives FG and g cover every positive g-run. These sets match the original three branches of S, while the complete nullable-omission and unit-closure constructions establish equivalence.

Common traps have direct corrections:

• For S -> ABA, keeping only ABA and B loses the distinct BA and AB variants.

• Treating every one-symbol right side as unit wrongly removes terminal rules such as G -> g.

• Checking only reachability keeps non-generating H; checking only generation keeps unreachable D and E.

• Copying one unit link instead of its transitive closure misses d and g at S.

Two quick checks expose unfinished work. If S -> B remains, unit elimination is incomplete. If D -> d remains in the final grammar, reachability was checked too early or not recomputed.

7. How exams test CFG simplification

Stable question forms ask you to identify nullable or useless symbols, choose an equivalent epsilon-free or unit-free grammar, select a safe elimination order, count the remaining productions or variables, or decide whether epsilon was preserved.

Question 52 in the official IIT Guwahati GATE 2026 question-paper and answer-key page uses a concrete CFG and asks which properties hold for strings in L(G). Solving it requires following productions and testing language claims rather than recalling a definition alone.

KnowledgeGate currently has more than ten practice questions on Simplification of CFG. The GATE CS Exam Preparation Courses & Test Series page is the broader map for related compiler-design and parsing practice.

8. The short version and next step

Use the checksum 1-4-5-6 for this grammar: one nullable variable, four variants from S -> ABA, five nontrivial unit closures listed above, and six surviving nonterminals. The safe order is epsilon variants, full unit closure, non-generating removal, and then reachability.

For a transfer exercise, add C -> epsilon to the original grammar. Before touching any unit rule, you should obtain NULLABLE = {A, C, B, S} because B -> C makes B nullable and every symbol in ABA can then vanish. Continue the remaining steps yourself.

Use GATE Guidance by Sanchit Sir for structured subject coverage, then use the GATE Test Series to apply the procedure under exam conditions.