Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 59 · Context-Free Grammars

Simplifying Context-Free Grammars

Learn how to simplify a context-free grammar by removing useless symbols, ε-productions and unit productions in the right order, with a Python implementation.

Grammars written by hand, and especially grammars produced by tools, often contain clutter: variables that can never produce a string, rules that can never be reached, ε-productions that make derivations shrink, and unit productions like A → B that only rename. Before a grammar is converted to a normal form or analyzed, it is standard to simplify it without changing its language (with one small exception for ε, explained below).

There are three kinds of cleanup. They must be done in a specific order.

Step 1: remove ε-productions

An ε-production is a rule A → ε. A variable is nullable if it can derive ε. Find all nullable variables by iteration:

  1. Every variable with a production A → ε is nullable.
  2. If A → X1 X2 ... Xk and all Xi are nullable variables, A is nullable.
  3. Repeat until nothing new appears.

Then replace each production by all versions in which any subset of its nullable symbols is deleted (and drop empty right sides). The grammar S → A b A, A → a | ε becomes S → A b A | b A | A b | b, A → a. The new grammar generates the same language except possibly the empty string: if ε ∈ L(G) it cannot be represented without an ε-rule, so we say the new grammar generates L(G) − {ε}. (Add a new start variable S' → S | ε if you need ε back.)

Step 2: remove unit productions

A unit production has the form A → B, one variable on the right. Compute the unit pairs (A, B), meaning A ⇒* B using only unit productions (start with (A, A) for every A and follow chains). Then for each unit pair (A, B) and each non-unit production B → α, add A → α. Finally delete all unit productions.

It is important to remove ε-productions first: they can create new unit productions (A → B C with C nullable gives A → B).

Step 3: remove useless symbols

A symbol is useless if it takes part in no derivation of a terminal string from S. Two conditions:

  • Non-generating variables derive no terminal string at all (like E → E e with no escape). Find the generating ones by iteration: a variable is generating if some production has a right side consisting only of terminals and generating variables. Delete the non-generating ones and every production that mentions them.
  • Unreachable symbols cannot be reached from the start symbol. Starting from S, follow the productions and keep only what you meet.

Order matters here too: first remove non-generating variables, then unreachable ones. Doing it backwards can leave useless symbols behind, because deleting non-generating variables can make other symbols unreachable.

The correct overall order

flowchart LR
    G["Original grammar"] --> E["1. Remove ε-productions"]
    E --> U["2. Remove unit productions"]
    U --> N["3. Remove non-generating variables"]
    N --> R["4. Remove unreachable symbols"]
    R --> S["Simplified grammar"]

ε-removal can create units; unit removal can create unreachable symbols; so do them in this order.

Implementing the cleanup

Here is a grammar with every kind of clutter:

TEXT
S -> A B | C
A -> a A | ε
B -> b B | b | D
C -> c
D -> E            (E can never produce a terminal string)
E -> E e
F -> f            (nothing ever uses F)
Python Simplify a grammar step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The final grammar has only S, A and B, with C folded into S by the unit-production step: S → A B | b B | b | c, A → a A | a, B → b B | b. Notice what disappeared: D, E and F (useless), the ε-rule for A, and the units S → C and B → D.

Checking that the language is preserved

You should never trust a transformation without testing it. A neat way to compare two grammars is to compute, by a fixed-point iteration, all strings of length at most n derivable from each variable: start with the empty sets, repeatedly add the concatenations the productions allow, and stop when nothing changes. This works even with ε-rules and recursion.

Python Compare the languages of two grammars

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two grammars agree on every string up to length 7. Here ε was not in the language to begin with: S needs at least one b or a c. If the original language had contained ε, the simplified grammar would lack it, and you would restore it with a fresh start symbol S' → S | ε.

Why simplify?

  • Smaller, faster parsers. Useless rules cost time and memory in every recognition run.
  • Correctness of later algorithms. Chomsky and Greibach normal form conversions assume a grammar without ε-rules, units and useless symbols.
  • Clarity. A simplified grammar is easier to read and to prove correct.

The relation between a grammar and the language it generates is that every grammar defines exactly one language, but every context-free language has infinitely many grammars. Simplification picks a canonical, tidy representative.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which variables are nullable in S → A B, A → a | ε, B → ε | b?

    A and B have ε-productions, and S → A B has only nullable variables on its right, so S is nullable too.
  2. 2. In what order should you remove non-generating and unreachable symbols?

    Deleting non-generating variables removes productions and can make other symbols unreachable. Doing it the other way round can leave useless symbols behind.
  3. 3. Why must ε-productions be removed before unit productions?

    Dropping a nullable symbol from a production can leave a single variable on the right, creating a unit production that would otherwise be missed.
  4. 4. What happens to ε when all ε-productions are removed from a grammar for a language containing ε?

    Without any ε-production nothing can derive the empty string. Add S' → S | ε when you need ε back.
  5. 5. For the unit pair (A, B), which productions are added to A?

    A can reach B through unit steps, then use any non-unit rule of B directly, so those rules are copied to A.

Summary

  • Simplification removes ε-productions, unit productions and useless symbols without changing the language (except ε itself).
  • Order: ε-productions, then unit productions, then non-generating variables, then unreachable symbols.
  • Nullable variables and unit pairs are found by simple fixed-point iteration.
  • Always verify by comparing the languages of both grammars on all short strings.

Next: Chomsky and Greibach Normal Forms