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