Course contentsShow
← Computer Science
Lesson 1821 of 2,87241. Context-Free LanguagesFree lesson

Converting CFGs to Chomsky Normal Form

Master the algorithm to transform any CFG into an equivalent CNF grammar.

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.