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-

1. Chomsky Normal Form (CNF)
2. Greibach Normal Form (GNF)

Chomsky Normal Form-

 A context free grammar is said to be in chomsky normal form (CNF) if all its productions are of the form-A → BC or A → awhere 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 → B1B2B3….Bn where n > 2 with A → B1C where C → B2B3….Bn.

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.

Problem-01:

Convert the given grammar to CNF-

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-

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 Ca and Cb.

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

Ca → a       ………..(5)

Cb → b       ………..(6)

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

A → CaB / CbAB         ………..(8)

Step-04:

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

CAB → AB       ………..(10)

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

A → CaB / CbCAB         ………..(12)

Step-05:

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

A → CaB / CbCAB

B → b

D → d

Ca → a

Cb → b

CAB → 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,

Watch this Video Lecture

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.