Chomsky Normal Form (CNF) is a special and simplified form of a Context-Free Grammar (CFG).
In simple words:
CNF converts CFG production rules into a very simple standard format.
It is mainly used in parsing, proofs, and algorithms related to context-free languages.
1. Rules of CNF
In Chomsky Normal Form, every production must have one of these forms:
Form 1:
\[ \boxed{A\rightarrow BC} \]
where B and C are non-terminals.
Form 2:
\[ \boxed{A\rightarrow a} \]
where a is a terminal.
Special Case:
The start symbol may have:\[ \boxed{S\rightarrow\epsilon} \]
if the language contains the empty string.
2. What is NOT Allowed?
In CNF, normally we do not allow:
❌ \(A\rightarrow B\)
❌ \(A\rightarrow aB\)
❌ \(A\rightarrow ABC\)
❌ \(A\rightarrow\epsilon\) for ordinary variables
The only allowed forms are:\[ A\rightarrow BC \]
or\[ A\rightarrow a \]
plus the special start-symbol rule \(S\rightarrow\epsilon\).
3. Simple Example
Suppose we have:\[ S\rightarrow aAB \]
This is not CNF because it contains a terminal and three symbols on the RHS.
We can introduce new variables.
Let:\[ C\rightarrow AB \]
and:\[ D\rightarrow a \]
Then:\[ S\rightarrow DC \]
Now all rules are in CNF:\[ S\rightarrow DC \]\[ C\rightarrow AB \]\[ D\rightarrow a \]
4. Another Example
Suppose:\[ S\rightarrow aB \]
This is not CNF because \(aB\) contains both a terminal and a variable.
Create a new variable:\[ A\rightarrow a \]
Then replace \(a\) with A:\[ S\rightarrow AB \]
Now:\[ S\rightarrow AB \]\[ A\rightarrow a \]
Both are valid CNF productions.
5. Steps to Convert CFG into CNF
This is important for exams.
Step 1: Remove ε-productions
Remove productions such as:\[ A\rightarrow\epsilon \]
except the special case involving the start symbol.
Step 2: Remove Unit Productions
Remove rules such as:\[ A\rightarrow B \]
Step 3: Remove Useless Symbols
Remove:
- Non-generating symbols
- Unreachable symbols
Step 4: Replace terminals in long productions
If we have:\[ A\rightarrow aB \]
introduce:\[ C\rightarrow a \]
Then:\[ A\rightarrow CB \]
Step 5: Break long productions
If:\[ A\rightarrow BCD \]
break it into two-variable productions:\[ A\rightarrow BX \]\[ X\rightarrow CD \]
Now every production follows:\[ A\rightarrow BC \]
6. CNF Conversion Example
Consider:\[ S\rightarrow aAB \]
We need to convert it into CNF.
Step 1: Replace terminal
Create:\[ C\rightarrow a \]
So:\[ S\rightarrow CAB \]
Step 2: Break three variables
Create:\[ D\rightarrow AB \]
Then:\[ S\rightarrow CD \]
Final grammar:\[ \boxed{S\rightarrow CD} \]\[ \boxed{D\rightarrow AB} \]\[ \boxed{C\rightarrow a} \]
All productions are now in CNF.
7. Why is CNF Important?
CNF is useful because:
- It gives a standard form for CFG.
- It simplifies grammar analysis.
- It is useful in parsing algorithms such as the CYK algorithm.
- It is useful in theoretical proofs.
- It makes CFG processing easier.
8. CNF vs CFG
| CFG | CNF |
|---|---|
| General form of CFG | Special form of CFG |
| Many types of productions allowed | Only restricted forms allowed |
| Example \(A\rightarrow aBC\) | Not allowed |
| \(A\rightarrow BC\) | Allowed |
| \(A\rightarrow a\) | Allowed |
| Used for general language description | Used for parsing and theoretical analysis |
⭐ Exam Answer — 5–10 Marks
Chomsky Normal Form (CNF) is a special form of Context-Free Grammar in which all production rules have a restricted structure.
The productions in CNF are:\[ \boxed{A\rightarrow BC} \]
where B and C are non-terminals, or:\[ \boxed{A\rightarrow a} \]
where a is a terminal.
If the language contains the empty string, the start symbol may also have:\[ \boxed{S\rightarrow\epsilon} \]
To convert a CFG into CNF, we generally:
- Remove ε-productions.
- Remove unit productions.
- Remove useless symbols.
- Replace terminals occurring in longer productions by new variables.
- Break productions having more than two variables on the RHS.
For example:\[ S\rightarrow aAB \]
can be converted into:\[ C\rightarrow a \]\[ D\rightarrow AB \]\[ S\rightarrow CD \]
Thus, all productions follow the CNF format.
🧠 Fast Memory Trick
Remember:
CNF = 2 Variables OR 1 Terminal
\[ \boxed{A\rightarrow BC\quad\text{or}\quad A\rightarrow a} \]
And conversion:
Remove ε → Remove Unit → Remove Useless → Replace Terminals → Break Long Rules.
