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:
- A → BC (a variable produces exactly two variables)
- 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.