Chomsky's normal form

Overview

Chomsky's normal form (CNF) is a method to simplify context-free grammar.

Every grammar in CNF is context-free, and every CFGContext-free grammar. can be converted into CNF.

Grammar is in CNF if all the productions follow either of the following set of rules:

• Start symbol generates null.
• A nonterminal generates two nonterminals.
• A nonterminal generates one terminal.

Steps to convert grammar to CNF

The following steps are used to convert context-free grammar into Chomsky's normal form.

1. Introduce a new start variable that produces the old start variable.
2. Remove the null productions from non-starting variables.
3. Remove the unit productions.
4. Convert all rules such that the right side has one terminal and two variables. New variables can be introduced to convert the rules.

Example

Let's consider the following CFG:

Step 1: Add a new start state

Step 2: Remove null productions

Remove null productions iteratively. Replace the values of the variables that produce null in any other production.

Step 2.1: Removing $B \rightarrow \epsilon$

Step 2.2: Removing $A \rightarrow \epsilon$

Step 3: Remove unit productions

Step 3.1: Replace the productions produced by $S$ in $S_0$ and $A$

Step 3.2: Replace the productions produced by $B$ in $A$

Step 4: Incorporate one terminal and two variables in each production

Step 4.1: Introduce $C \rightarrow a$ where $a$ occurs with a variable

Step 4.2: Introduce $D \rightarrow AS$ where $AS$ occurs with another variable

Result

The following grammar is in CNF.

Note: A single CFG can produce different Chomsky's normal forms.