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