Chomsky Normal Form | Normal Forms in Automata

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)

 

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-

BC or a

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 → 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.

 

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 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-

S → CaAD                  ………..(7)

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

 

Step-04:

 

Replace AD and AB by new variables CAD and CAB respectively.

 

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

CAD → AD       ………..(9)

CAB → AB       ………..(10)

 

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

S → CaCAD                  ………..(11)

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

 

Step-05:

 

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

 

S → CaCAD

A → CaB / CbCAB

B → b

D → d

Ca → a

Cb → b

CAD → AD

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.

Summary
Chomsky Normal Form | Normal Forms in Automata
Article Name
Chomsky Normal Form | Normal Forms in Automata
Description
A grammar is called in Chomsky Normal Form if all its productions derive either two non-terminals or a single terminal. Examples. Normal Forms- Chomsky Normal Form and Greibach Normal Form.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-