CFG Simplification & Chomsky Normal Form

Why a normal form?

A context-free grammar can have rules of any shape. Many algorithms and proofs are much simpler if every rule has one of a few fixed forms. Chomsky normal form (CNF) allows only:

Rule	Example
A → B C (exactly two variables)	S → A C1
A → a (exactly one terminal)	Ua → a
S0 → ε (only the start variable, only if ε is in the language)	S0 → ε

With CNF, every parse tree is a binary tree, and a string of length n takes exactly 2n − 1 rule uses. The CYK algorithm needs CNF to parse any context-free language in O(n³). Every context-free grammar can be converted, and the language stays the same.

The steps

Step	What it removes	How
1. START	the start symbol on a right side	add S0 → S
2. DEL	ε-rules A → ε	find the nullable variables; add copies of every rule with nullable symbols left out
3. UNIT	unit rules A → B	A inherits every non-unit rule of each variable it reaches through unit rules
4. USELESS	variables that can never finish, or can’t be reached	delete them and every rule that uses them
5a. TERM	terminals inside long rules	new variable Ua → a, used in place of a
5b. BIN	rules with 3 or more symbols	A → X1 X2 X3 becomes A → X1 C, C → X2 X3

The order matters. DEL creates new unit rules, so UNIT must come after it. Both steps can leave variables unreachable, so USELESS comes after them.

Worked example

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

1. START. S appears in S → ASA, so add S0 → S.

2. DEL. B → ε makes B nullable, and A → B makes A nullable too. Every rule containing A or B gets copies with those symbols left out:

S0 → S
S  → ASA | AS | SA | S | aB | a
A  → B | S
B  → b

3. UNIT. The unit rules are S0 → S, S → S, A → B and A → S. Each variable inherits the rules it reaches through them, and S → S just disappears:

S0 → ASA | AS | SA | aB | a
S  → ASA | AS | SA | aB | a
A  → b | ASA | AS | SA | aB | a
B  → b

4. USELESS. Every variable can finish and can be reached, so nothing is removed.

5a. TERM. a appears inside aB, so add Ua → a and write Ua B instead.

5b. BIN. ASA is too long, so add C1 → S A and write A C1 instead. The final grammar is:

S0 → A C1 | A S | S A | Ua B | a
S  → A C1 | A S | S A | Ua B | a
A  → b | A C1 | A S | S A | Ua B | a
B  → b
Ua → a
C1 → S A

Every rule is now A → BC or A → a. Press Convert in the model to watch each step.

Useless symbols

A variable is useless if it can never finish, or if no derivation from the start reaches it:

• In S → AB ∣ aC ∣ b, B → bB, B only ever produces more B’s. It never finishes (it can’t derive a string of terminals), so B and the rule S → AB are deleted.
• After that, nothing uses A any more, so A is unreachable, and so is D in D → d.

Always remove the variables that can’t finish first, then the unreachable ones. Doing it the other way round can leave useless rules behind.

Code

from itertools import product

is_var = lambda s: s[0].isupper()

def to_cnf(g, start):
    """g: {head: [body, ...]}, body = tuple of symbols, () = ε. Capitals are variables."""
    # 1. START: a new start variable if the old one appears on a right side
    if any(start in b for bs in g.values() for b in bs):
        g, start = {'S0': [(start,)], **g}, 'S0'
    # 2. DEL: find nullable variables, add copies without them, drop ε-rules
    nul = set()
    while True:
        new = {h for h, bs in g.items() if any(all(s in nul for s in b) for b in bs)}
        if new <= nul: break
        nul |= new
    def variants(b):
        spots = [i for i, s in enumerate(b) if s in nul]
        for keep in product((True, False), repeat=len(spots)):
            drop = {i for i, k in zip(spots, keep) if not k}
            yield tuple(s for i, s in enumerate(b) if i not in drop)
    g = {h: list(dict.fromkeys(v for b in bs for v in variants(b) if v))
            + ([()] if h == start and start in nul else []) for h, bs in g.items()}
    # 3. UNIT: inherit the non-unit rules of every variable reachable by A → B
    unit = lambda b: len(b) == 1 and is_var(b[0])
    def reach(h):
        seen = [h]
        for x in seen:
            seen += [b[0] for b in g[x] if unit(b) and b[0] in g and b[0] not in seen]
        return seen
    g = {h: list(dict.fromkeys(b for x in reach(h) for b in g[x] if not unit(b))) for h in g}
    # 4. USELESS: keep variables that can finish, then those reachable from the start
    gen = set()
    while True:
        new = {h for h, bs in g.items() if any(all(not is_var(s) or s in gen for s in b) for b in bs)}
        if new <= gen: break
        gen |= new
    g = {h: [b for b in bs if all(not is_var(s) or s in gen for s in b)] for h, bs in g.items() if h in gen}
    seen = [start]
    for x in seen:
        seen += [s for b in g.get(x, []) for s in b if is_var(s) and s not in seen]
    g = {h: bs for h, bs in g.items() if h in seen}
    # 5a. TERM: a terminal inside a long rule gets its own variable Ua → a
    extra = {}
    def term(b):
        if len(b) < 2: return b
        for s in b:
            if not is_var(s): extra.setdefault(f'U{s}', [(s,)])
        return tuple(s if is_var(s) else f'U{s}' for s in b)
    g = {h: list(dict.fromkeys(term(b) for b in bs)) for h, bs in g.items()}
    g.update(extra)
    # 5b. BIN: A → X1 X2 X3 … becomes A → X1 C, C → X2 X3 … (equal tails share C)
    out, tails = {h: [] for h in g}, {}
    def short(b):
        if len(b) <= 2: return b
        if b[1:] not in tails:
            tails[b[1:]] = v = f'C{len(tails) + 1}'
            out[v] = [short(b[1:])]
        return (b[0], tails[b[1:]])
    for h, bs in g.items():
        out[h] = list(dict.fromkeys(out[h] + [short(b) for b in bs]))
    return out, start

g = {'S': [('A', 'S', 'A'), ('a', 'B')], 'A': [('B',), ('S',)], 'B': [('b',), ()]}
cnf, start = to_cnf(g, 'S')
for h, bs in cnf.items():
    print(h, '→', ' | '.join(' '.join(b) or 'ε' for b in bs))
# S0 → A C1 | A S | S A | Ua B | a
# S → A C1 | A S | S A | Ua B | a
# A → b | A C1 | A S | S A | Ua B | a
# B → b
# Ua → a
# C1 → S A

We checked the converted grammars against the originals on every string up to length 6, using CYK.

Another normal form

Greibach normal form (GNF) requires every rule to start with a terminal: A → a B1 B2 … Bk. Every derivation step then produces exactly one terminal, which makes GNF handy for building pushdown automata.

Common mistakes

• Deleting ε-rules without adding the copies. Then strings that needed the empty variable are lost.
• Losing the empty string. If ε is in the language, keep S0 → ε (and only that ε-rule).
• Removing unit rules before ε-rules. ε-removal can create new unit rules, such as S → S.
• Stopping too early. A → aB is still not CNF: the terminal needs its own variable.
• Removing unreachable symbols before the ones that can’t finish. Do the “can’t finish” check first, then the reachability check.