Chomsky Normal Form
What You'll Learn
You'll learn what Chomsky Normal Form (CNF) is and why restricting context-free grammar productions to two specific shapes makes grammars easier to analyze and use in algorithms.
What is Chomsky Normal Form?
Chomsky Normal Form is a restricted version of context-free grammars where every production follows one of exactly two patterns:
- A → BC (a variable produces exactly two variables)
- A → a (a variable produces exactly one terminal symbol)
Plus, if the grammar generates the empty string, we allow S → ε only for the start symbol S, which must not appear on the right side of any production.
Why CNF Matters
Think of CNF as a "standardized format" for grammars—like converting measurements to metric units. It doesn't change what language the grammar generates, but it makes the grammar uniform and predictable.
This standardization is crucial for parsing algorithms. When every production either splits into exactly two variables or outputs a single terminal, you can easily predict:
- Parse tree shape: All internal nodes have exactly 2 children or 1 terminal child
- Derivation length: For a string of length n, you need exactly 2n - 1 steps
- Parsing complexity: The CYK (Cocke-Younger-Kasami) algorithm relies on CNF to run in O(n³) time
Structure Example
A CNF grammar for simple arithmetic might look like:
S → AB
A → a
B → CD
C → b
D → c
Notice: every production is either two variables or one terminal—nothing else.
Key Takeaway: Chomsky Normal Form restricts CFG productions to exactly two forms (A → BC or A → a), creating a standardized structure that simplifies parsing algorithms and theoretical analysis without changing the language the grammar generates.