Chomsky Normal Form
In CNF ,each production must be of the form S->AB or S->a
Example 1 Convert given CFG into CNF
S-> Aba |aBA
A-> baB |ƛ
B-> aBa |b
Step 1 : Elimination of NULL production [ƛ production ]
A -> ƛ is the only null production
Therefore A variable is nullable
A present /A absent/A present /A absent( which is null so not represented)
S -> ABa | Ba | aBA | aB
A present /A absent
A -> bAB | bB
B -> aBa | b
Step 2 : Elimination of UNIT production [S->A ]{ that is if 1 variable derives another variable eliminate it}
In CFG,there is only 1 unit production S -> A
Substitute the value of A in S
S -> ABa | Ba | aB | bAB | bB
A -> bAB | bB
B -> aBa | b
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 -> ABA1 | BA1 | A1B |B1 | B1B
A -> B1AB | B1B
B -> A1BA1 | b
A1 -> a
B1 -> b
Step 4 : final CFG
S -> AX | BA1 | A1B | B1YA -> B1Y | B1BB -> A1X | bX -> B A1 A1 -> aY -> AB B1 -> b
Conversion of CFG [context free grammar ] to CNF [ chomsky normal form ] | Example 1