1 of 10

Session 7 and 8: �Chomsky normal form (CNF)

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 10

Chomsky Normal Form

2

Each productions has form:

variable

variable

or

terminal

Amity School of Engineering & Technology

3 of 10

Conversion From CFG to CNF

Amity School of Engineering & Technology

4 of 10

Conversion From CFG to CNF

Steps to convert CFG to CNF

Step 1. Eliminate start symbol from RHS.

If start symbol S is at the RHS of any production in the grammar, create a new production as:

S0->S

where S0 is the new start symbol.

​

Step 2. Eliminate null, unit and useless productions.

If CFG contains null, unit or useless production rules, eliminate them.

​

Step 3. Eliminate terminals from RHS if they exist with other terminals or non-terminals.

e.g,; production rule X->xY can be decomposed as:

X->ZY

Z->x

​

Step 4. Eliminate RHS with more than two non-terminals.

e.g,; production rule X->XYZ can be decomposed as:

X->PZ

P->XY

Amity School of Engineering & Technology

5 of 10

5

Examples:

Not Chomsky

Normal Form

Chomsky

Normal Form

Amity School of Engineering & Technology

6 of 10

Conversion to Chomsky Normal Form

​

Example:

6

Not Chomsky

Normal Form

Amity School of Engineering & Technology

7 of 10

7

Introduce variables for terminals:

Amity School of Engineering & Technology

8 of 10

8

Introduce intermediate variable:

Amity School of Engineering & Technology

9 of 10

9

Introduce intermediate variable:

Amity School of Engineering & Technology

10 of 10

10

Final grammar in Chomsky Normal Form:

Initial grammar

Amity School of Engineering & Technology