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

Chomsky Normal Form (CNF)

Understand CNF where productions are A → BC or A → a, and why it's useful.

Chomsky Normal Form (CNF)

What you'll learn: You'll understand how Chomsky Normal Form standardizes context-free grammar productions into two simple patterns and why this simplification is valuable.

What is Chomsky Normal Form?

Chomsky Normal Form is a restricted format for context-free grammars where every production rule follows one of just two patterns:

  1. A → BC (a variable produces exactly two variables)
  2. A → a (a variable produces exactly one terminal)

Additionally, if the empty string is in the language, you're allowed S → ε where S is the start symbol, and S cannot appear on the right side of any production.

Why These Restrictions?

Think of CNF like standardizing ingredients in recipes. Instead of "add 1-3 eggs or some flour mixture," you'd say "add 1 egg" or "combine flour with sugar." The recipe becomes predictable and easier to analyze.

With CNF, every derivation step either:

  • Splits one variable into two (branching the parse tree), or
  • Terminates by producing a single terminal symbol

This uniformity makes algorithms easier to design and prove correct.

Why CNF is Useful

CNF is the foundation for many parsing and decision algorithms:

  • Predictable parse tree height: A string of length n has derivations with exactly 2n - 1 steps
  • CYK parsing algorithm: Uses CNF to efficiently parse strings in O(n³) time
  • Theoretical proofs: Simplifies reasoning about context-free languages

Converting any CFG to CNF doesn't change the language it generates (except possibly the empty string), so you lose no expressive power—just gain structure.

Key Takeaway: Chomsky Normal Form standardizes CFG productions to A → BC or A → a, creating a uniform structure that enables efficient algorithms and clearer theoretical analysis.