Converting CFGs to Chomsky Normal Form
You'll learn the systematic algorithm to transform any context-free grammar into an equivalent Chomsky Normal Form grammar.
Why Convert to CNF?
Remember that Chomsky Normal Form restricts productions to A → BC (two variables) or A → a (single terminal). Real-world CFGs rarely follow these rules naturally. Converting to CNF is like reformatting a document into a standard template—it doesn't change the language, but makes it easier to analyze algorithmically.
The Conversion Algorithm
The transformation follows four systematic steps:
1. Add a New Start Symbol
Create S₀ → S where S was the original start symbol. This ensures the start symbol never appears on the right side of any production.
2. Eliminate ε-Productions
Remove all rules like A → ε (except S₀ → ε if the empty string is in the language). For each A → ε, modify every rule containing A on the right to include versions with and without A.
3. Eliminate Unit Productions
Remove rules like A → B (one variable producing another). Replace them by adding copies of all B's productions to A.
4. Convert Long Productions
For any production with more than 2 symbols on the right (like A → BCD), introduce new variables to break it down: A → BX, X → CD.
Replace terminals in mixed productions using new variables: if you have A → aB, create T_a → a and rewrite as A → T_aB.
Example Sketch
If you have S → aSb | ab, you'd introduce T_a → a, T_b → b, then create intermediate variables to satisfy CNF rules.
Key Takeaway: Converting to CNF is a mechanical four-step process (new start, eliminate ε-rules, eliminate unit rules, break long productions) that preserves the language while standardizing the grammar structure.