conversion of CFG [context free grammar ] to CNF [ chomsky normal form ] | Example 3

Chomsky Normal Form

In CNF ,each production must be of the form S->AB or S->a

Example 2   Convert given CFG into CNF

S-> AACD
A-> abA |ƛ
C ->aC | a  | ƛ
D ->  DaD |  cA

Step 1 : Elimination of NULL production [ƛ production ]

A -> ƛ and C -> ƛ are  the  null productions
Therefore A and C variable are nullable

both A abd c present /1 A and c present /c  present / both  A present  and C absent/ only 1 A present /both A and C absent
S ->     AACD  |  ACD  |   CD    | AAD  | AD | D

A present /A absent
A -> abA    | ab
C ->  aC | a
D -> DaD | CA | C | A 

 Step 2 : Elimination of UNIT  production [S->A ]{ that is if 1 variable derives another variable eliminate it}

replace  D -> DaD | CA | C | A  in S and also replace C and A in A

S ->     AACD  |  ACD  |   CD    | AAD  | AD | D |  D a D | CA | C | A

therefore, 

S ->     AACD  |  ACD  |   CD    | AAD  | AD | D |  D a D | CA | aC | a | abA    | ab

A -> abA    | ab
C ->  aC | a
D -> DaD | CA | 
aC | a | abA    | ab


 Step 3 : Restrict the right side of the production to 2 or more variables or 1 terminal symbol by substitution of new variables

Replace a with A1 and b with B1

S ->     AACD  |  ACD  |   CD    | AAD  | AD | D |  D A1 D | CA |  A1 C | a | A1 B1 A    | A1 B1

A -> A1 B1 A    | A1 B1
C ->  A1 C | a
D -> D A1 D | CA | 
A1 C | a | A1 B1 A    | A1 B1

A1 -> a
B1 -> b
C1 -> c


 Step 4 : final CFG


S ->    XY  |  AY |   CD    | XD  | AD | D |  P D | CA |  A1 C1 | a | Q A    | A1 B1

A -> Q A    | A1 B1
C ->  A1 C | a
D -> P D | CA | A1 C | a | Q A    | A1 B1

X ->   A B1     A1 -> a.

Y  ->  A A1        B1  -> b.

Z -> B B1.

P -> D A1
Q -> A1 B1 
conversion of CFG [context free grammar ] to CNF [ chomsky normal form ] | Example 3