Question

convert the following grammar to Chomsky Normal Form

S -> D0S1 | 1

D -> F0D1 | 0 | e | FG

F -> SF | DD | S

G -> GK | DG

Answer 1

A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules satisfy one of the following conditions:

• A ->a
• B ->CD
• S-> ε

GIVEN grammer :S -> D0S1 | 1

D -> F0D1 | 0 | e | FG

F -> SF | DD | S

G -> GK | DG

FIRSTLY we will check whether the grammer is in cnf form:- The given grammer is not in cnf form

1) Create new start variable:-

S0 -> S

S -> D0S1 | 1

D -> F0D1 | 0 | e | FG

F -> SF | DD | S

G -> GK | DG

2) Eliminate unit production F -> S, Also removal of unit production S->S and S0->S from grammar yields: :-

S0 -> D0S1 | 1

S -> D0S1 | 1

D -> F0D1 | 0 | e | FG

F -> SF | DD | D0S1 | 1 // NEW PRODUCTION

G -> GK | DG

3) Removing useless variables and productions:-

S0 -> D0S1|1

S -> D0S1 | 1 (1 is generated from S so, it is useful)

D -> F0D1 | 0 | e | FG (0 is generated from D so, it is useful)

F -> D0S1

G -> GK | DG

4) Delete all the REMOVING production  which is present in LHS as well as RHS:-

S0 -> D0S1|1

S -> D0S1 | 1  

D -> 0 |e

F -> D0S1

G -> GK | DG

5) THIS is the converted cnf

S0 -> D0S1|1

S -> D0S1 | 1  

D -> 0

J -> e

F -> D0S1

G -> GK | DG