Convert CFG to CNF:
1. Removal of λ – Productions
2. Removal of Unit Productions
3. Convert CFG production to CNF production (V → VV | T).
When we convert CFG to CNF, grammar does not have any λ – productions or any unit production.
If it has λ – productions or any unit production we have to remove it.
Let consider a grammar that has no λ – productions or any unit production. And we are going to convert it to the corresponding CNF production rule (V → VV | T)
The given grammar is CFG but not CNF because the production rule of CNF is
V→VV | T where we never allowed non-terminal (variable) with the terminal.
Step 1: Initially to remove the terminals with non-terminals (variable) we use some variables
If we see the above productions some of the productions follow CNF production rules like,
But some of the productions above not follow CNF productions rules like
Now we introduce additional variables to get the productions into the normal form of CNF:
We get the final grammar:
Now it is in CNF.