Skills101

AdvancedTheory of Computation (TOC) · Lesson 13 of 14 · Updated ·

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

The context-free grammars lesson 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:

KindExampleWhy it is a problem
ε-productionB → εa derivation can shrink, so the length of a sentential form tells you nothing
unit productionA → Ba step that only renames; it can even form cycles (A → B, B → A)
useless symbola variable that never helps produce a terminal stringdead 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.
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)
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

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

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:

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)
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:

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])
  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 what you learned

📝 Quiz: Simplifying CFGs and CNF5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →