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-> AbAa |bA
A-> AaB |ƛ
B-> Bb |Sa
Step 1 : Elimination of NULL production [ƛ production ]
A -> ƛ is the only null production
Therefore A variable is nullable
both A present /1 A present /1 A present / both A absent/A present /A absent
S -> AbAa | Aba | bAa | ba | bA | b
A present /A absent
A -> AaB | aB
B -> BBb | Sa
Step 2 : Elimination of UNIT production [S->A ]{ that is if 1 variable derives another variable eliminate it}
SKIPPED since there is no unit production.
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 -> A B1 A A1 | A B1 A1 | B1 A A1 | B1 A1 | B1 A | b
A -> A A1 B | A1 B
B -> BB B1 | S A1
A1 -> a
B1 -> b
Step 4 : final CFG
S -> X Y | X A1 | B1 Y | B1Y | B1 A | b.
A -> Y B | A1 B.
B -> B Z | S A1 .
X -> A B1 A1 -> a.
Y -> A A1 B1 -> b.
Z -> B B1.
Conversion of CFG [context free grammar ] to CNF [ chomsky normal form ] | Example 2