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
A present /A absent
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
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