CNF from S-->aAD;A->aB/bAB;B->b,D->d.

RGPV 2020   
Find the grammar in Chomsky Normal form equivalent to S-->aAD;A->aB/bAB;B->b,D->d.

Ans. A context free grammar (CFG) is said to be in chomsky normal form (CNF) if all its productions are of the form-

1. A → BC 
2. A → a

where A, B, C are non-terminals and a is a terminal.

This CFG S-->aAD;A->aB/bAB;B->b,D->d, can be written as

1. S --> aAD, Not in CNF
2. A --> aB, Not in CNF
3. A --> bAB, Not in CNF
4. B --> b, In CNF
5. D --> d, In CNF
6. E --> a, Generate new production, In CNF
7. F --> AD, Generate new production, In CNF
8. G --> AB, Generate new production, In CNF

Select 1 production:

S --> aAD

can be written as 

S --> EAD, (E --> a)

S --> EF, (F --> AD)

Now its in CNF.

Select 2 production:

A --> aB

can be written as

A --> EB, (E --> a)

Now its in CNF.

Select 3 prodcution:

A --> bAB

can be written as

A --> BAB, (B --> b)

A --> BG, (G --> AB)

Now its in CNF.

So, CNF of CFG given in question is:

S --> EF, Not in CNF

A --> EB, Not in CNF

A --> BG, Not in CNF

B --> b, In CNF

D --> d, In CNF

E --> a, Generate new production, In CNF

F --> AD, Generate new production, In CNF

G --> AB, Generate new production, In CNF