← 🌳 Context-Free Grammars & Languages
Subtopic 3 of 5

3.3Simplification and normal forms

The idea

Simplifying a grammar means removing ε-rules, unit rules and useless symbols; then it can be put in Chomsky normal form.

Think of it like this: Tidying a workshop before building: clear out clutter, then arrange tools into a standard layout.

Why it exists

CNF makes parsing algorithms (CYK) and proofs simple, and gives fixed derivation lengths.

How it works

  1. Remove A → ε by adding versions of rules with A deleted.
  2. Remove unit rules A → B by copying B's rules into A.
  3. Remove symbols that generate nothing or are unreachable.
  4. CNF: every rule is A → BC or A → a; GNF: A → aα.

Worked example: S → aSb | ab in CNF

S → T_a X | T_a T_b; X → S T_b; T_a → a; T_b → b. A string of length n then needs exactly 2n − 1 derivation steps.

Now play with it

  • →Step through "Simplify" on the ε example and watch the production counts.
  • →Open the CNF tab and verify the two rule shapes.
Examples

Original

S -> A B C A -> a A | ε B -> b B | ε C -> c | ε

(press Next step)

  • Original: 7 productions
  • 1. Remove ε-productions: 14 productions
  • 2. Remove unit productions: 24 productions
  • 3. Remove useless symbols: 15 productions
  • 4. Chomsky Normal Form: 18 productions

Check yourself

In a CNF grammar, a string of length 5 needs how many derivation steps?

Remember: CNF: length n ⇒ 2n − 1 steps. GNF: n steps.
Exam notes (the dense version)

Remove ε-productions, then unit productions, then useless symbols. CNF: every rule is A → BC or A → a (a string of length n takes exactly 2n − 1 steps). GNF: every rule is A → aα (n steps for length n).

Previous year questions: Context-Free Grammars & Languages (13)

PYQs are grouped by topic, so this is the full set for Context-Free Grammars & Languages; try the ones that match this subtopic. Open all 13 on the topic page.