Artificial Intelligence & Data Science is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Simplification of CFGs

How to simplify a context-free grammar by removing useless symbols, ε-productions, and unit productions while preserving the language (up to ε), with exact algorithms and worked examples.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers use simplified context-free grammars (CFGs) when designing parsers, compilers, and program analysers. A simplified grammar is smaller, easier to understand, easier to convert to normal forms (like Chomsky Normal Form) and more efficient for parser generators and proofs about languages.

Key ideas

Start with definitions (simple English). Bold each defined term.

  • Context-free grammar (CFG): A 4-tuple G = (V, Σ, R, S) where V is a finite set of non-terminals (or variables), Σ is a finite set of terminals, R is a finite set of productions (rules) of the form A → α with A ∈ V and α ∈ (V ∪ Σ), and S ∈ V is the start symbol. The grammar generates a language L(G) ⊆ Σ.

  • Production: a rule A → α meaning non-terminal A can be rewritten as string α.

  • ε-production: a production of the form A → ε, where ε is the empty string.

  • Unit production: a production of the form A → B where A and B are non-terminals.

  • Nullable non-terminal (or nullable): a non-terminal A is nullable if A ⇒* ε (A can derive the empty string).

  • Generating non-terminal (or simply generating): a non-terminal A is generating if A ⇒* w for some w ∈ Σ* (i.e., A can derive a string of only terminals).

  • Reachable non-terminal (or reachable): a non-terminal A is reachable if S ⇒* αAβ for some α, β ∈ (V ∪ Σ)* (i.e., A appears in some sentential form from S).

  • Useless symbol: a non-terminal that is not both generating and reachable. Such symbols (and their productions) can be removed without changing L(G).

Key simplification tasks universities expect and the assumptions behind each:

  1. Removing non-generating symbols (also called eliminating symbols that do not derive terminal strings).

    • Algorithm (standard): compute the set G0 = {A ∈ V | there exists A → w with w ∈ Σ*}. Iteratively compute Gi+1 = Gi ∪ {A | there exists A → α and every symbol in α is either in Gi or in Σ}. Stop when fixed point Gk. Then Gk is the set of generating non-terminals. Remove all productions with a non-terminal not in Gk and remove those non-terminals from V. This preserves L(G) because any derivation producing terminals uses only generating symbols; non-generating symbols cannot produce terminal strings.

    • Exam derivation to show correctness: show (1) no string w ∈ Σ* can be derived using a non-generating symbol (so removing them does not remove any derivation of terminal strings), and (2) any derivation using only generating symbols remains, so the language is preserved.

  2. Removing unreachable (non-reachable) symbols.

    • Algorithm: compute R0 = {S}. Iteratively Ri+1 = Ri ∪ {B | there exists A ∈ Ri and a production A → α with B appearing in α}. Stop at fixed point Rk. Remove non-terminals not in Rk and their productions. Draw diagram to explain: draw directed graph with nodes V and an edge A → B if some production A → α contains B; then reachable is nodes reachable from S.

    • Proof idea: productions unreachable from S never appear in any S-derivation, so removing them does not change L(G).

  3. Eliminating ε-productions (except possibly for start symbol if ε ∈ L(G)).

    • Goal: produce grammar G' with no ε-productions (A → ε) but L(G') = L(G) \ {ε} or L(G') = L(G) if handled specially.

    • Algorithm (standard): a) Compute the nullable set N of all non-terminals that derive ε. Initialize N = {A | A → ε ∈ R}. Iteratively add A if there exists a production A → X1 X2 ... Xn (n ≥ 1) where every Xi is a non-terminal in N. Stop at the least fixed point. b) For every production A → α, consider every subset of nullable non-terminals in α and add a production A → β where β is α with those nullable non-terminals removed, except do not add the identical α again and do not add A → ε at this stage unless you plan to allow ε in final language. After adding all such productions, remove all original ε-productions (except possibly S → ε if ε ∈ L(G) must be preserved). If the start S ∈ N (nullable), create a new start symbol S0 and add S0 → S | ε to preserve ε if required.

    • Important assumption and caution: This construction preserves L(G) except that it removes ε unless you explicitly add it back using S0. State this precisely in exam answers.

  4. Eliminating unit productions.

    • Algorithm: compute the unit-pair relation. For each A, compute UNIT(A) = {B | A ⇒* B using only unit productions}. This is the reflexive transitive closure of unit edges. For each A and each B ∈ UNIT(A), and for each non-unit production B → γ (γ not a single non-terminal), add A → γ. After doing this for all A, remove all unit productions.

    • Proof: any derivation using unit chains A ⇒* B followed by B ⇒ γ can be replaced by A ⇒ γ in the new grammar; conversely, any A ⇒ γ in new grammar can be traced to some B used previously, so languages are equal.

Order to apply steps in practice: remove non-generating symbols first, then remove unreachable symbols, then eliminate ε-productions (with care about the start), and finally remove unit productions. This order avoids creating new useless symbols repeatedly. After each step, re-run useless-symbol elimination (both generating and reachable) to remove any new useless symbols.

Diagrams to draw in an exam: draw directed graph of non-terminals with edges A → B if a production A → α contains B (label edges optionally with the full α). For unit-elimination show unit-edges A → B. For nullable computation you can annotate each non-terminal with a tick when found nullable.

Formulas

For a CFG simplification topic we list syntax and short formula-like items to remember.

A -> α means non-terminal A rewrites to string α where α ∈ (V ∪ Σ)*. (A is a non-terminal, Σ terminals)

A -> ε means A rewrites to the empty string ε (an ε-production).

nullable(G) = least fixed point of {A | A -> ε or A -> X1 X2 ... Xn with each Xi nullable} where Xi are non-terminals.

generating(G) = least fixed point of {A | A -> w with w ∈ Σ* or A -> α where every non-terminal in α is generating}.

reachable(G) = least fixed point of {S} ∪ {B | A in set and A -> α with B in α}.

Unit closure: UNIT(A) = {B | A ⇒* B using only unit productions}. After closure, add A -> γ for every B in UNIT(A) and every non-unit B -> γ.

Worked examples

Example 1 — remove useless symbols, ε, and units

Given grammar G: V = {S,A,B,C,D,E} Σ = {a,b,d,e} R: S -> A B | C A -> a A | ε B -> b C -> D D -> d E -> e

Step 1: Generating set.

  • Productions that are directly terminal-only: B -> b, D -> d, E -> e. So G0 = {B, D, E}.
  • Is C generating? C -> D and D ∈ G0 so add C. Now G1 = {B, D, E, C}.
  • Is A generating? A -> a A uses terminal a and A; but we need A to be generating: since A can go to aA and A is not yet in set, but A -> ε gives A generating. So A ∈ G because A -> ε. Add A: G2 = {A,B,C,D,E}.
  • S -> A B uses A and B, both in G2, so S ∈ G. Final generating set is {S,A,B,C,D,E} (everything generating) because A -> ε made it generating and reachable will decide removal of E.

Step 2: Reachable set from S.

  • R0 = {S}.
  • From S -> A B and S -> C add A,B,C. R1 = {S,A,B,C}.
  • From C -> D add D. R2 = {S,A,B,C,D}.
  • E is never reached. So remove E and the production E -> e.

Step 3: Eliminate ε-productions.

  • Nullable set N: A -> ε so A ∈ N. No other nullable (B, C, D, S are not nullable because they require terminals). So N = {A}.
  • For each production with A occurrences create variants with A removed:
    • S -> A B produces also S -> B (remove A).
    • A -> a A produces A -> a (removing the nullable A on right) and A -> a A (original). Also keep A -> ε for now following algorithm then remove ε-productions later.
    • No other productions contain A.
  • Remove original ε-production A -> ε. Because S is not nullable we do not need new start symbol.
  • New R now: S -> A B | C | B ; A -> a A | a ; B -> b ; C -> D ; D -> d.

Step 4: Eliminate unit productions.

  • Unit productions present: S -> C, C -> D. Compute unit closures:

    • UNIT(S) contains S, C, D (S->C->D)
    • UNIT(C) contains C, D
    • UNIT(D) contains D
  • For each A in V add non-unit productions from UNIT(A):

    • From D: D -> d is non-unit. So add C -> d, S -> d.
    • From C: originally C had only unit C->D; after adding C->d it's fine.
  • Remove unit productions S->C and C->D.

  • Final grammar G': S -> A B | B | d A -> a A | a B -> b D -> d (D is still present but now unreachable? Check reachability)

  • Recompute reachable: from S we reach A and B only. D is not reachable from S (S -> d uses a terminal directly and does not pass through D). Therefore D is unreachable and can be removed along with its production D -> d.

Final simplified grammar (cleaned): S -> A B | B | d A -> a A | a B -> b

This grammar has no ε-productions, no unit productions, and no useless symbols. The language is preserved (note original G could produce ε? No, S couldn't derive ε because A could be ε but S -> A B requires B which produces b, so ε is not in L(G)).

Answer (bold final grammar):

S -> A B | B | d A -> a A | a B -> b

Example 2 — unit elimination with start nullable

G: V={S,A,B}, Σ={a} R: S -> A | a A -> B B -> ε

Step 1: Nullable set: B is nullable (B -> ε), hence A is nullable (A -> B), hence S is nullable (S -> A). So N = {B, A, S}.

Since S is nullable we must preserve ε: introduce a new start symbol S0 and add S0 -> S | ε. Now eliminate ε-productions and then unit productions. The resulting simplified grammar is: S0 -> a | ε This generates the original language {ε, a} and has no ε-productions except at the start symbol.

Common mistakes

  • When adding productions after removing nullable symbols, accidentally adding the original production again or adding duplicate productions is okay but confusing; be explicit about excluding duplicates.
  • In unit elimination, forgetting to copy non-unit productions of a B into every A that has A ⇒* B via units.
  • Trying to remove non-generating symbols before noticing a production A -> ε that makes them generating; order matters practically.

For your exam

Typical question types: give a CFG and ask to simplify it (show steps), prove correctness of an algorithm (for removing useless symbols, ε, or unit productions), or draw the reachability graph. A full-marks answer includes:

  • Clear statement of definitions used (nullable, generating, reachable).
  • Exact sequence of algorithm steps with intermediate sets and fixed-point stops.
  • Reconstructed final grammar and short proof/sketch why L(G) is preserved (mention ε handling).
  • If asked, draw or describe the directed graph used for reachability and unit-closure.

Quick check

  1. What is a unit production?
  2. If the start symbol S is nullable, what extra step must you do when eliminating ε-productions?
  3. State the stopping condition when computing the generating set.

Answers: 1) A production A -> B where A,B are non-terminals. 2) Introduce a new start S0 and add S0 -> S | ε to preserve ε. 3) Stop when the set does not grow (fixed point).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?