**Normal Forms-**

Normalization is performed in order to standardize the grammar. |

- By reducing the grammar, the grammar gets minimized but does not gets standardized.
- This is because the RHS of productions have no specific format.
- In order to standardize the grammar, normalization is performed using normal forms.

**Types of Normal Forms-**

The most frequently used normal forms are-

- Chomsky Normal Form (CNF)
- Greibach Normal Form (GNF)

In this article, we will discuss about Chomsky Normal Form.

**Chomsky Normal Form-**

A context free grammar is said to be in chomsky normal form (CNF) if all its productions are of the form-
where A, B, C are non-terminals and a is a terminal. |

From here, we infer-

- To be in CNF, all the productions must derive either two non-terminals or a single terminal.
- CNF restricts the number of symbols on the right side of a production to be two.
- The two symbols must be non-terminals or a single terminal.

**Example-**

S → AB

A → a

B → b

This context free grammar is in chomsky normal form.

**Steps-**

The following steps are followed to standardize the grammar using CNF-

**Rule-01:**

Reduce the grammar completely by-

- Eliminating ∈ productions
- Eliminating unit productions
- Eliminating useless productions

**Also Watch-** **How To Reduce Grammar?**

**Rule-02:**

Replace each production of the form A → B_{1}B_{2}B_{3}….B_{n} where n > 2 with A → B_{1}C where C → B_{2}B_{3}….B_{n}.

Repeat this step for all the productions having more than two variables on RHS.

**Rule-03:**

Replace each production of the form A → aB with A → XB and X → a.

Repeat this step for all the productions having the form A → aB.

**PRACTICE PROBLEMS BASED ON CHOMSKY NORMAL FORM-**

**Problem-01:**

Convert the given grammar to CNF-

S → aAD

A → aB / bAB

B → b

D → d

**Solution-**

**Step-01:**

The given grammar is already completely reduced.

**Step-02:**

The productions already in chomsky normal form are-

B → b ………..(1)

D → d ………..(2)

These productions will remain as they are.

The productions not in chomsky normal form are-

S → aAD ………..(3)

A → aB / bAB ………..(4)

We will convert these productions in chomsky normal form.

**Step-03:**

Replace the terminal symbols a and b by new variables C_{a} and C_{b}.

This is done by introducing the following two new productions in the grammar-

C_{a} → a ………..(5)

C_{b} → b ………..(6)

Now, the productions (3) and (4) modifies to-

S → C_{a}AD ………..(7)

A → C_{a}B / C_{b}AB ………..(8)

**Step-04:**

Replace AD and AB by new variables C_{AD} and C_{AB} respectively.

This is done by introducing the following two new productions in the grammar-

C_{AD} → AD ………..(9)

C_{AB} → AB ………..(10)

Now, the productions (7) and (8) modifies to-

S → C_{a}C_{AD} ………..(11)

A → C_{a}B / C_{b}C_{AB} ………..(12)

**Step-05:**

From (1), (2), (5), (6), (9), (10), (11) and (12), the resultant grammar is-

S → C_{a}C_{AD}

A → C_{a}B / C_{b}C_{AB}

B → b

D → d

C_{a} → a

C_{b} → b

C_{AD} → AD

C_{AB} → AB

This grammar is in chomsky normal form.

**Problem-02:**

Convert the given grammar to CNF-

S → 1A / 0B

A → 1AA / 0S / 0

B → 0BB / 1S / 1

**Solution-**

**Step-01:**

The given grammar is already completely reduced.

**Step-02:**

The productions already in chomsky normal form are-

A → 0 ………..(1)

B → 1 ………..(2)

These productions will remain as they are.

The productions not in chomsky normal form are-

S → 1A / 0B ………..(3)

A → 1AA / 0S ………..(4)

B → 0BB / 1S ………..(5)

We will convert these productions in chomsky normal form.

**Step-03:**

Replace the terminal symbols 0 and 1 by new variables C and D.

This is done by introducing the following two new productions in the grammar-

C → 0 ………..(6)

D → 1 ………..(7)

Now, the productions (3), (4) and (5) modifies to-

S → DA / CB ………..(8)

A → DAA / CS ………..(9)

B → CBB / DS ………..(10)

**Step-04:**

Out of (8), (9) and (10), the productions already in Chomsky Normal Form are-

S → DA / CB ………..(11)

A → CS ………..(12)

B → DS ………..(13)

These productions will remain as they are.

The productions not in chomsky normal form are-

A → DAA ………..(14)

B → CBB ………..(15)

We will convert these productions in Chomsky Normal Form.

**Step-05:**

Replace AA and BB by new variables E and F respectively.

This is done by introducing the following two new productions in the grammar-

E → AA ………..(16)

F → BB ………..(17)

Now, the productions (14) and (15) modifies to-

A → DE ………..(18)

B → CF ………..(19)

**Step-06:**

From (1), (2), (6), (7), (11), (12), (13), (16), (17), (18) and (19), the resultant grammar is-

S → DA / CB

A → CS / DE / 0

B → DS / CF / 1

C → 0

D → 1

E → AA

F → BB

This grammar is in chomsky normal form.

To gain better understanding about Chomsky Normal Form,

**Next Article-** **Algorithm To Decide Whether CFL Is Empty**

Get more notes and other study material of **Theory of Automata and Computation.**

Watch video lectures by visiting our YouTube channel **LearnVidFun.**