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

A grammar can look smaller after you cross out a few rules and still be wrong. You may miss an epsilon effect, expand only part of a unit chain, or remove useful symbols in the wrong order. The example applies all three transformations and shows every intermediate production. The goal is a smaller grammar with the same language. If the original start symbol can derive epsilon, preserving the empty string requires a fresh start symbol.

CFG simplification: what is removed and what must stay

An epsilon-production has the form A -> epsilon. A unit production has one nonterminal alone on its right-hand side, as in A -> B. Therefore, A -> b and A -> BC are not unit productions. A useless symbol is either non-generating, meaning it cannot derive a terminal string, or unreachable from the start symbol.

Use this order: eliminate epsilon-productions, eliminate unit productions, remove non-generating symbols, then remove unreachable symbols. Each stage can expose the work needed in the next, so recompute the relevant sets instead of deleting rules by appearance.

The invariant is that terminal strings in the language must not change. The wider Theory of Computation map places this operation within the subject, while Context-Free Grammars and Pushdown Automata explains the CFG and PDA bridge. The relevant operation is grammar transformation.

Eliminate epsilon-productions by computing the full nullable set

Compute nullable variables to a fixed point. First mark every variable that directly produces epsilon. Then mark a variable if every symbol in any one of its right-hand sides is already nullable. Repeat until a pass adds nothing.

Suppose X -> ABC and Nullable = {A, C}. Independently omitting A and C gives four distinct alternatives: ABC, BC, AB, and B. The count is four, not three and not eight, because B is not nullable.

There is one essential exception. If the original start symbol S is nullable, first introduce S0 -> S | epsilon. You can then remove the other epsilon-productions without silently deleting the empty string from the language.

For the grammar in this example, only A is nullable. Consequently,

Eliminate unit productions through transitive unit closure

Define Unit(A) as the set containing A and every variable reachable from it using only unit-production edges. After epsilon removal in the running grammar, the exact closures are Unit(S) = {S, B, C, D} and Unit(B) = {B, D}. The chain S -> B -> D shows why direct, one-pass substitution is incomplete.

For each variable, copy the non-unit productions of every endpoint in its unit closure. This gives S -> AB | bB | c | d and B -> bB | d. We can now delete S -> B, S -> C, and B -> D. We temporarily retain C -> c and D -> d because reachability has not yet been recomputed.

The copied alternatives preserve the language. Inlining C -> c creates S -> c. Inlining B -> D -> d creates both B -> d and S -> d. If you merely delete the unit edges, those terminal strings disappear.

Remove useless symbols in the safe order: generating before reachable

First compute generating variables to a fixed point. Mark a variable with a terminal-only or epsilon alternative, then propagate the mark through productions whose nonterminals are already generating. Remove every non-generating variable and every production mentioning one. Only then start from S, follow the surviving productions, and remove variables that are not reachable.

After unit elimination, S, A, B, C, D, E are generating. F is not, because F -> fF has no terminating base case. Once F is removed, only S, A, B are reachable from S. Thus C, D, E are generating but unreachable and must also go.

The order matters because a symbol can appear reachable only through a branch that is later proved non-generating. Remove such dead material first, then recompute reachability on what remains. Recursion alone never proves generation: F -> fF cannot finish, whereas E -> eE | e can finish through E -> e.

Fully worked CFG simplification from 11 alternatives to 8

Take V = {S, A, B, C, D, E, F}, T = {a, b, c, d, e, f}, and start symbol S. The original 11 alternatives are:

S -> AB | C
A -> aA | epsilon
B -> bB | D
C -> c
D -> d
E -> eE | e
F -> fF

Its language is L(G) = {a^i b^j d | i, j >= 0} union {c}. Neither E nor F contributes because neither is reachable from S.

After epsilon removal, there are 12 alternatives:

S -> AB | B | C
A -> aA | a
B -> bB | D
C -> c
D -> d
E -> eE | e
F -> fF

After unit removal, there are 13 alternatives:

S -> AB | bB | c | d
A -> aA | a
B -> bB | d
C -> c
D -> d
E -> eE | e
F -> fF

Removing non-generating F and then unreachable C, D, E leaves exactly eight alternatives:

S -> AB | bB | c | d
A -> aA | a
B -> bB | d

Now verify representative strings. The string abbd derives as S => AB => aB => abB => abbB => abbd. The string c derives directly. The string d is the case i = 0, j = 0. In contrast, epsilon, e, and f are rejected.

AB generates the cases with i >= 1; bB generates i = 0, j >= 1; and d supplies i = j = 0. The separate

How CFG simplification is tested, and the traps that cost marks

Typical questions ask you to find the nullable set, count distinct alternatives after epsilon removal, compute a transitive unit closure, or identify the generating and reachable variables. You may also need to choose the final equivalent grammar. For X -> ABC with Nullable = {A, C}, remember that the exact answer is four alternatives.

Use this compact correction list:

• If S is nullable, add a fresh start symbol before removing epsilon-productions.

• Do not call A -> a a unit production. Its right-hand side is a terminal.

• Follow unit edges transitively, not only one edge deep.

• Compute generating first, then reachability on the surviving grammar.

• Do not call F -> fF generating when it has no terminating base case.

• Count right-hand-side alternatives, not display lines. The final three lines contain eight alternatives.

After untimed hand practice, the GATE Test Series provides timed Theory of Automata tests. That describes KnowledgeGate's own practice coverage, not an official exam-pattern claim.

CFG simplification: the short version and next step

Use one executable checklist: compute nullable variables and add every distinct omission variant; preserve epsilon with a fresh start symbol where necessary; compute transitive unit closures; mark generating variables to a fixed point; recompute reachability from S; and test representative accepted and rejected strings.

In this example, 11 original alternatives become the equivalent eight-alternative grammar S -> AB | bB | c | d, A -> aA | a, B -> bB | d, generating exactly {a^i b^j d | i, j >= 0} union {c}.

For a sequenced learning route across the subject, use GATE Guidance by Sanchit Sir. If you want to browse related subject and exam resources first, start with GATE CS Exam Preparation. Both are structured next steps after you can reproduce this transformation without looking at the answer.