# Simplifying Context-Free Grammars — Useless Symbols, ε-Rules, Unit Rules and Step-by-Step Conversion to CNF

Source: https://skills101.in/learn/theory-of-computation/toc-cfg-simplification-normal-forms — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-21.

The [context-free grammars lesson](https://skills101.in/learn/theory-of-computation/context-free-grammar-pda) showed a grammar already in **Chomsky Normal Form (CNF)** and ran the CYK algorithm on it. Exams usually give you a messy grammar instead and ask you to **simplify it and convert it to CNF**. This is a fixed procedure with a few traps. In this lesson we do it step by step on one grammar, and a Python program does each step too, so you can check your hand work.

## 1. Three kinds of rules that cause trouble

A **production** (rule) has a variable on the left and a string of variables and terminals on the right. Three kinds of rules make a grammar harder to use:

| Kind | Example | Why it is a problem |
|---|---|---|
| **ε-production** | B → ε | a derivation can shrink, so the length of a sentential form tells you nothing |
| **unit production** | A → B | a step that only renames; it can even form cycles (A → B, B → A) |
| **useless symbol** | a variable that never helps produce a terminal string | dead rules make the grammar bigger and confuse proofs |

Removing them never changes the language, except for the empty string ε, which we keep with one special rule if the language contains it.

Two definitions:

- A variable X is **generating** if X ⇒* w for some string w of terminals only.
- A variable X is **reachable** if S ⇒* αXβ, that is, X appears in some sentential form derived from the start symbol.
- A symbol is **useful** only if it is both. Otherwise it is **useless**.

## 2. Removing useless symbols — order matters

Take the grammar S → AB | a, A → b, B → BC, C → c.

- **Generating:** A (gives b), C (gives c), S (gives a). B is **not** generating: every B-rule contains B again, so it never finishes.
- Delete B and every rule that uses it. S → AB disappears.
- **Reachable** (now): only S. A and C can no longer be reached, so delete them too.

```python
g = {"S": [("A", "B"), ("a",)], "A": [("b",)], "B": [("B", "C")], "C": [("c",)]}

def generating(g):
    gen, changed = set(), True
    while changed:
        changed = False
        for v, bodies in g.items():
            if v not in gen and any(all(s in gen or s.islower() for s in b) for b in bodies):
                gen.add(v)
                changed = True
    return gen

def reachable(g, start):
    seen, todo = {start}, [start]
    while todo:
        for b in g.get(todo.pop(), []):
            for s in b:
                if s.isupper() and s not in seen:
                    seen.add(s)
                    todo.append(s)
    return seen

def keep(g, ok):
    return {v: [b for b in bs if all(s in ok or s.islower() for s in b)] for v, bs in g.items() if v in ok}

gen = generating(g)
print("generating:", sorted(gen))
g1 = keep(g, gen)
g2 = keep(g1, reachable(g1, "S"))
print("after step 1:", g1)
print("after step 2:", g2)

wrong = keep(keep(g, reachable(g, "S")), generating(g))
print("wrong order:", wrong)
```

```text
generating: ['A', 'C', 'S']
after step 1: {'S': [('a',)], 'A': [('b',)], 'C': [('c',)]}
after step 2: {'S': [('a',)]}
wrong order: {'S': [('a',)], 'A': [('b',)], 'C': [('c',)]}
```

The last line shows the trap. If you first remove unreachable symbols and **then** non-generating ones, A and C survive even though they are useless. The rule is: **non-generating first, then unreachable**.

## 3. The worked example

We will now clean this grammar (a standard textbook example):

> S → ASA | aB  A → B | S  B → b | ε

It has an ε-rule (B → ε), unit rules (A → B, A → S) and S appears on a right side. The safe order of steps is:

![Five steps in order: add a new start symbol S0, remove ε-rules, remove unit rules, remove useless symbols with non-generating first, then convert to CNF](https://skills101.in/learn-img/theory-of-computation/cfg-cleanup-order.svg)

**Step 1 — new start symbol.** Add S0 → S. Now the start symbol never appears on a right side, so later steps cannot accidentally give it new jobs.

## 4. Removing ε-productions

**Find the nullable variables.** X is **nullable** if X ⇒* ε. Start with variables that have a rule X → ε, then repeat: X is nullable if some rule X → Y₁…Yₖ has only nullable symbols on the right.

- B → ε, so B is nullable.
- A → B, so A is nullable.
- S → ASA needs S to be nullable, and S → aB contains the terminal a, so S is **not** nullable.

**Expand every rule.** For each rule, add every version obtained by deleting any subset of its nullable symbols. Then delete all ε-rules (keep S0 → ε only if S0 is nullable).

![Table for S → ASA with A nullable: keeping or dropping each A gives the bodies A S A, A S, S A and S](https://skills101.in/learn-img/theory-of-computation/cfg-epsilon-expand.svg)

Similarly S → aB gives S → aB | a, and A → B stays (A → ε would be the empty version, which we drop).

## 5. Removing unit productions

A unit rule has a single variable on the right, like A → B. For each variable X, find every variable Y that X can reach **using unit rules only** (including X itself). Then give X all the **non-unit** bodies of those Y.

- S0 reaches S (S0 → S). So S0 gets all of S's non-unit bodies.
- A reaches B and S. So A gets b (from B) and all of S's bodies.
- The rule S → S is a unit rule to itself; it simply disappears.

The program below does steps 1, 4 and 5:

```python
from itertools import product

# S -> ASA | aB,  A -> B | S,  B -> b | ε      (an empty tuple () means ε)
g = {"S": [("A", "S", "A"), ("a", "B")], "A": [("B",), ("S",)], "B": [("b",), ()]}

def show(g):
    for v, bodies in g.items():
        print(f"  {v:3} -> " + " | ".join(" ".join(b) or "ε" for b in bodies))

def nullable(g):
    nul, changed = set(), True
    while changed:
        changed = False
        for v, bodies in g.items():
            if v not in nul and any(all(s in nul for s in b) for b in bodies):
                nul.add(v)
                changed = True
    return nul

def remove_epsilon(g, start):
    nul = nullable(g)
    new = {"S0": [(start,)] + ([()] if start in nul else [])}   # new start never appears on a right side
    for v, bodies in g.items():
        out = []
        for b in bodies:
            choices = [[(s,), ()] if s in nul else [(s,)] for s in b]
            for pick in product(*choices):
                body = tuple(s for part in pick for s in part)
                if body and body not in out:
                    out.append(body)
        new[v] = out
    return new

def remove_units(g):
    def is_unit(b):
        return len(b) == 1 and b[0] in g
    new = {}
    for v in g:
        reach, todo = {v}, [v]                  # every B with v =>* B using unit rules only
        while todo:
            for b in g[todo.pop()]:
                if is_unit(b) and b[0] not in reach:
                    reach.add(b[0])
                    todo.append(b[0])
        new[v] = []
        for u in sorted(reach, key=list(g).index):
            for b in g[u]:
                if not is_unit(b) and b not in new[v]:
                    new[v].append(b)
    return new

print("nullable:", sorted(nullable(g)))
g1 = remove_epsilon(g, "S")
print("after removing ε-rules:")
show(g1)
g2 = remove_units(g1)
print("after removing unit rules:")
show(g2)
```

```text
nullable: ['A', 'B']
after removing ε-rules:
  S0  -> S
  S   -> A S A | A S | S A | S | a B | a
  A   -> B | S
  B   -> b
after removing unit rules:
  S0  -> A S A | A S | S A | a B | a
  S   -> A S A | A S | S A | a B | a
  A   -> A S A | A S | S A | a B | a | b
  B   -> b
```

Check by hand: no rule now has ε on the right, and no rule is a single variable. B is still used (in aB), and every variable is generating and reachable, so step 4 of the procedure removes nothing here.

## 6. Converting to Chomsky Normal Form

In CNF every rule must be **A → BC** (exactly two variables) or **A → a** (exactly one terminal), plus S0 → ε if needed. Two small steps finish the job:

1. **Terminals in long bodies.** In a rule with two or more symbols, replace each terminal a by a new variable Ta and add Ta → a. So S → aB becomes S → Ta B.
2. **Long bodies.** Split A → X₁X₂X₃ into A → X₁Y and Y → X₂X₃. A body of length k needs k − 2 new variables. You may **reuse** a new variable when the same tail appears again, as Y1 → S A does here.

The program converts the grammar and then compares the strings of length up to 7 generated by the **original** grammar and by the CNF grammar:

```python
def words(g, start, n):
    """All terminal strings of length <= n that the grammar derives (fixpoint, works with ε and unit rules)."""
    gen = {v: set() for v in g}
    changed = True
    while changed:
        changed = False
        for v, bodies in g.items():
            for b in bodies:
                parts = {""}
                for s in b:
                    options = gen[s] if s in g else {s}
                    parts = {p + q for p in parts for q in options if len(p + q) <= n}
                if not parts <= gen[v]:
                    gen[v] |= parts
                    changed = True
    return gen[start]

def to_cnf(g):
    new, tails = {v: [] for v in g}, {}

    def pair(b):                                 # step 2: X1 X2 X3 ... -> X1 Y, where Y -> X2 X3 ...
        if len(b) == 2:
            return b
        if b[1:] not in tails:
            tails[b[1:]] = f"Y{len(tails) + 1}"
            new[tails[b[1:]]] = [pair(b[1:])]
        return (b[0], tails[b[1:]])

    for v, bodies in g.items():
        for b in bodies:
            if len(b) == 1:                      # A -> a is already fine
                new[v].append(b)
                continue
            b = tuple(s if s in g else "T" + s for s in b)
            for s in b:                          # step 1: each terminal in a long body gets Ta -> a
                if s not in g:
                    new.setdefault(s, [(s[1:],)])
            new[v].append(pair(b))
    return new

original = {"S": [("A", "S", "A"), ("a", "B")], "A": [("B",), ("S",)], "B": [("b",), ()]}
no_units = {"S0": [("A", "S", "A"), ("A", "S"), ("S", "A"), ("a", "B"), ("a",)],
            "S":  [("A", "S", "A"), ("A", "S"), ("S", "A"), ("a", "B"), ("a",)],
            "A":  [("A", "S", "A"), ("A", "S"), ("S", "A"), ("a", "B"), ("a",), ("b",)],
            "B":  [("b",)]}
cnf = to_cnf(no_units)
for v, bodies in cnf.items():
    print(f"  {v:3} -> " + " | ".join(" ".join(b) for b in bodies))
print("every rule is A -> BC or A -> a:",
      all((len(b) == 2 and all(s in cnf for s in b)) or (len(b) == 1 and b[0] not in cnf)
          for bodies in cnf.values() for b in bodies))
w1, w2 = words(original, "S", 7), words(cnf, "S0", 7)
print("same strings up to length 7:", w1 == w2, "-", len(w1), "strings, e.g.", sorted(w1, key=lambda w: (len(w), w))[:6])
```

```text
  S0  -> A Y1 | A S | S A | Ta B | a
  S   -> A Y1 | A S | S A | Ta B | a
  A   -> A Y1 | A S | S A | Ta B | a | b
  B   -> b
  Y1  -> S A
  Ta  -> a
every rule is A -> BC or A -> a: True
same strings up to length 7: True - 247 strings, e.g. ['a', 'aa', 'ab', 'ba', 'aaa', 'aab']
```

The two grammars generate exactly the same strings, so no step changed the language.

**Greibach Normal Form (GNF)** is the other normal form in many syllabi: every rule is A → aα, a terminal followed by zero or more variables. Converting to GNF also needs left recursion to be removed, and is usually asked only as a short definition question.

## Common mistakes

- Removing unreachable symbols before non-generating ones. Always non-generating first.
- Forgetting a combination when removing ε. A body with k nullable symbols gives up to 2ᵏ versions.
- Dropping S0 → ε when ε is in the language. If S was nullable, the language contains ε and must keep it.
- Removing unit rules before ε-rules. Removing ε can create new unit rules (S → S, S0 → S here), so ε goes first.
- Leaving a terminal inside a long body, like A → aB. In CNF it must become A → Ta B.

## Quick recap

- Generating: derives a terminal string. Reachable: appears from S. Useless: fails either test.
- Order: new start S0 → ε-rules → unit rules → useless symbols → CNF.
- Nullable set: grow it until nothing changes; expand bodies with every subset of nullable symbols dropped.
- Unit rules: X gets every non-unit body of every Y it reaches by unit rules.
- CNF: Ta → a for terminals in long bodies, then split long bodies into pairs.
- Always check with a program: same strings before and after.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/toc-cfg-simplification-normal-forms