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

- A → BC
- 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

- S –> aAD, Not in CNF
- A –> aB, Not in CNF
- A –> bAB, 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

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