A context-free grammar can have productions of any shape: long bodies, mixtures of terminals and variables, ε-productions, unit productions. That freedom is nice for humans writing grammars, but painful for algorithms and proofs. It is much easier to reason about a grammar where every production looks the same.
Chomsky Normal Form (CNF), named after the linguist Noam Chomsky, is the most widely used such standard shape.
A context-free grammar is in Chomsky Normal Form if every production has one of the forms A → BC (two variables) or A → a (one terminal), where A, B, C are variables and a is a terminal. If ε is in the language, the production S → ε is also allowed, provided the start symbol S does not appear on the right side of any production.
In this chapter we will see why CNF is useful, convert grammars into CNF step by step, and solve the typical GATE questions about it. It builds directly on the Simplification of CFGs chapter. Every CNF grammar below was produced by a program implementing the conversion and checked against the original grammar on all strings up to length 7 to 12.
Why CNF?
In CNF, a parse tree has a very regular shape. Every interior node either has exactly two variable children (A → BC) or exactly one terminal child (A → a). So the tree is a binary tree sitting on top of a row of terminal leaves.
CNF parse tree for "aabb" with S → AC | AB, C → SB, A → a, B → b
S
/ \
A C
| / \
a S B
/ \ \
A B b
| |
a bThis regularity gives us several facts that are used again and again:
Derivation length is fixed. A string of length n ≥ 1 is derived in exactly 2n − 1 steps: n − 1 steps of the form A → BC (each one increases the number of symbols by 1, from 1 up to n) and n steps of the form A → a (one per terminal).
Parse trees are binary. If the longest root-to-leaf path in a parse tree has k edges, the yield has length at most 2k−1. This is the key fact behind the Pumping Lemma for Context-Free Languages.
Membership can be decided by dynamic programming. Since every split is into exactly two parts, a table over substrings works. That is the CYK Algorithm, which requires a CNF grammar.
No ε or unit productions. Sentential forms never shrink and derivations cannot loop, so membership is clearly decidable.
Is This in CNF? Quick Check
Production | CNF? | Reason |
|---|---|---|
A → BC | Yes | two variables |
A → a | Yes | one terminal |
A → aB | No | terminal mixed with a variable |
A → BCD | No | body too long |
A → B | No | unit production |
A → ab | No | two terminals |
A → ε (A not the start symbol) | No | ε-production |
S → ε (S is start, not on any right side) | Yes | the only allowed exception |
A note on conventions. Hopcroft–Ullman define CNF for languages without ε and allow S on right sides. Sipser allows S → ε but then forbids S on any right side, which is why his algorithm always starts by adding a new start symbol. Both describe the same idea; for exam answers, add S0 → S whenever ε is in the language and S appears on a right side.
The Conversion Algorithm
Every context-free language without ε has a CNF grammar (and with ε, the S → ε exception covers it). The conversion is mechanical:
New start symbol (if needed). If S appears on a right side and ε ∈ L, add S0 → S and make S0 the start.
Remove ε-productions. (Remember whether S was nullable.)
Remove unit productions.
Remove useless symbols. Steps 2 to 4 are exactly the Simplification of CFGs algorithms, in that order.
Replace terminals in long bodies. In every body of length ≥ 2, replace each terminal a by a new variable Xa, and add Xa → a. Now every body is either a single terminal or a string of ≥ 2 variables.
Break long bodies. Replace A → B1B2…Bk (k ≥ 3) by a chain:
A → B1 C1 C1 → B2 C2 C2 → B3 C3 ... C(k-2) → B(k-1) Bk (k - 2 new variables)Put back ε. If the original start was nullable, add S0 → ε (or S → ε if S is not on any right side).
Steps 5 and 6 never create ε or unit productions, so the result is in CNF.
Example 1: { anbn | n ≥ 1 }
S → aSb | abε is not in the language, so no new start symbol is needed. There are no ε-productions, no unit productions and no useless symbols. Steps 2 to 4 change nothing.
Step 5 (terminals). Introduce A → a and B → b:
S → ASB | AB
A → a
B → bStep 6 (break long bodies). ASB has length 3. Replace it by S → AC with C → SB:
S → AC | AB
C → SB
A → a
B → bThis is in CNF. Derivation of aabb (n = 4, so 2·4 − 1 = 7 steps):
S ⇒ AC ⇒ aC ⇒ aSB ⇒ aABB ⇒ aaBB ⇒ aabB ⇒ aabbCount them: AC, aC, aSB, aABB, aaBB, aabB, aabb. Seven steps, as promised. (The tree drawn at the start of the chapter is this derivation.)
Example 2: Balanced Strings with ε
Let a stand for "(" and b for ")":
S → aSb | SS | εStep 1. ε ∈ L and S appears on right sides, so add a new start:
S0 → S
S → aSb | SS | εStep 2 (ε). Nullable: S, and therefore S0. From aSb we get aSb and ab. From SS we get SS and S; S → S is pointless, drop it. S0 → S has no shorter non-empty version. Remember: ε must be put back at the end.
S0 → S
S → aSb | ab | SSStep 3 (units). The unit pair (S0, S) copies all S-bodies to S0:
S0 → aSb | ab | SS
S → aSb | ab | SSStep 4 (useless). All symbols are generating and reachable.
Step 5 (terminals). A → a, B → b:
S0 → ASB | AB | SS
S → ASB | AB | SS
A → a
B → bSteps 6 and 7. Break ASB using X → SB, then add S0 → ε:
S0 → AX | AB | SS | ε
S → AX | AB | SS
X → SB
A → a
B → bS0 never appears on a right side, so S0 → ε is allowed. Derivation of abab (7 steps):
S0 ⇒ SS ⇒ ABS ⇒ aBS ⇒ abS ⇒ abAB ⇒ abaB ⇒ ababExample 3: The Expression Grammar
E → E + T | T
T → T * F | F
F → ( E ) | aε ∉ L, so we keep E as the start (Hopcroft style).
Step 2. No nullable variables.
Step 3 (units). Unit pairs (E, T), (E, F), (T, F). As computed in the previous chapter:
E → E + T | T * F | ( E ) | a
T → T * F | ( E ) | a
F → ( E ) | aStep 4. Nothing is useless.
Step 5 (terminals). P → +, M → *, L → (, R → ). The single-terminal body a stays as it is.
E → E P T | T M F | L E R | a
T → T M F | L E R | a
F → L E R | aStep 6 (break bodies). Three different length-3 bodies, each needing one new variable. The same tail is shared wherever it occurs:
Body | Becomes | New production |
|---|---|---|
E P T | E C1 | C1 → P T |
L E R | L C2 | C2 → E R |
T M F | T C3 | C3 → M F |
Final CNF grammar:
E → E C1 | T C3 | L C2 | a
T → T C3 | L C2 | a
F → L C2 | a
C1 → P T
C2 → E R
C3 → M F
P → +
M → *
L → (
R → )Derivation of a + a (length 3, so 5 steps):
E ⇒ E C1 ⇒ a C1 ⇒ a P T ⇒ a + T ⇒ a + aExample 4: ε in the Language, Many Nullable Symbols
S → ABA
A → aA | ε
B → bB | εThe language is a*b*a*, which includes ε. S does not appear on any right side, so no new start symbol is needed; we will keep S → ε at the end.
Step 2 (ε). Nullable: A, B, and S (all of ABA is nullable). S → ABA gives 7 non-empty versions, but some coincide: ABA, AB, AA, BA, A, B. A → aA gives aA, a; B → bB gives bB, b.
S → ABA | AB | AA | BA | A | B
A → aA | a
B → bB | bStep 3 (units). Unit pairs (S, A) and (S, B) copy aA, a, bB, b to S:
S → ABA | AB | AA | BA | aA | a | bB | b
A → aA | a
B → bB | bStep 5 (terminals). X → a, Y → b replace terminals in aA and bB:
S → ABA | AB | AA | BA | XA | a | YB | b
A → XA | a
B → YB | b
X → a
Y → bSteps 6 and 7. ABA becomes AC with C → BA. Add S → ε.
S → AC | AB | AA | BA | XA | YB | a | b | ε
C → BA
A → XA | a
B → YB | b
X → a
Y → bNotice that C → BA happens to equal one of S's own bodies; a new variable is still needed because C is not S.
How Big Does the Grammar Get?
Step | Effect on size |
|---|---|
Replace terminals | at most one new variable per terminal symbol |
Break a body of length k | k − 2 new variables and productions |
Unit removal | can copy many bodies (quadratic growth in the worst case) |
ε-removal | a body with m nullable symbols gives up to 2m − 1 versions |
Doing the body-breaking step before ε-removal keeps every body at length ≤ 2, so each body has at most 3 non-empty versions. With that ordering the CNF grammar is only polynomially (about quadratically) larger than the original.
CNF Compared with GNF
Feature | Chomsky Normal Form | Greibach Normal Form |
|---|---|---|
Production shape | A → BC or A → a | A → aα (one terminal followed by variables) |
Derivation length for |w| = n | exactly 2n − 1 | exactly n |
Parse tree shape | binary | each step emits one terminal |
Main use | CYK, CFL pumping lemma | PDA construction, proofs about derivation length |
GNF is covered in the next chapter, Greibach Normal Form.
Common Mistakes
Skipping simplification. If you break bodies before removing unit productions, you will still have A → B in the "final" grammar.
Leaving a terminal inside a body. A → aB is not CNF. Replace a with Xa → a.
Replacing a lone terminal. A → a is already in CNF. Do not turn it into A → Xa, which would be a unit production.
Losing ε. If the original language contains ε, the CNF grammar must have S → ε (with S not on any right side).
Keeping S → ε while S appears on a right side. Then S could vanish inside other derivations. Add a fresh start symbol first.
Saying derivations take 2n steps. It is 2n − 1: n terminal steps plus n − 1 binary steps.
GATE and Interview Questions
Q1. A grammar is in CNF. How many steps are needed to derive a string of length 10?
Exactly 2·10 − 1 = 19. Nine steps use A → BC (to grow from 1 symbol to 10), and ten steps use A → a (one per terminal).
Q2. Which of these productions are in CNF? S → AB, A → a, B → bC, C → CD, D → d, E → F
S → AB, A → a, C → CD and D → d are in CNF. B → bC mixes a terminal with a variable, and E → F is a unit production.
Q3. Convert S → aSa | bSb | c to CNF.
No ε, unit or useless symbols. Introduce A → a, B → b: S → ASA | BSB | c. Break the long bodies: S → AC1 | BC2 | c, C1 → SA, C2 → SB, A → a, B → b.
Q4. In a CNF parse tree, how many nodes are labelled with variables if the yield has length n?
2n − 1. There are n nodes using A → a (one above each leaf) and n − 1 binary nodes (a binary tree with n leaves, counting those n nodes as its leaves, has n − 1 internal nodes). This matches the 2n − 1 derivation steps: one step per variable node.
Q5. A production A → B1B2…B6 is converted to CNF. How many new variables are introduced?
k − 2 = 4: A → B1C1, C1 → B2C2, C2 → B3C3, C3 → B4C4, C4 → B5B6.
Q6. If the longest path in a CNF parse tree has 4 edges, what is the maximum length of its yield?
24−1 = 8. The last edge on every path goes from a variable to its single terminal, and the variables above it form a binary tree of height at most 3, which has at most 23 = 8 leaves.
Q7. Why can a CNF grammar not generate ε without the special S → ε rule?
Both production forms produce at least one terminal eventually: A → a produces one, and A → BC produces two variables that each must produce at least one terminal. So every derived terminal string has length ≥ 1.
Summary
CNF productions are only A → BC or A → a, plus S → ε when ε is in the language and S is not on any right side.
Conversion: (new start) → remove ε → remove units → remove useless → replace terminals in long bodies → break long bodies into pairs → put back ε.
A body of length k needs k − 2 new variables.
In CNF, a string of length n has a derivation of exactly 2n − 1 steps, and every parse tree is binary.
A yield of length n needs a tree whose longest path has at least ⌈log2 n⌉ + 1 edges.
CNF is the input format for the CYK Algorithm and the basis of the Pumping Lemma for Context-Free Languages.
CNF turns every parse tree into a binary tree. Most algorithms and proofs about context-free languages start from that shape.