Skip to content
Home » Chomsky Normal Form (CNF)

Chomsky Normal Form (CNF)

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

CFGCNF
General form of CFGSpecial form of CFG
Many types of productions allowedOnly restricted forms allowed
Example \(A\rightarrow aBC\)Not allowed
\(A\rightarrow BC\)Allowed
\(A\rightarrow a\)Allowed
Used for general language descriptionUsed 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:

  1. Remove ε-productions.
  2. Remove unit productions.
  3. Remove useless symbols.
  4. Replace terminals occurring in longer productions by new variables.
  5. 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.