FOR FREE CONTENT

How to convert CFG to CNF:

Convert CFG to CNF:

1. Removal of λ – Productions   

(Please in previous chapter Procedure to remove null production).

2. Removal of Unit Productions 

(Please in previous chapter Removal of unit production).

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)

Example:

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 ${\mathbf{P}}_{\mathbf{a}}\mathbf{,}\mathbf{ }{\mathbf{P}}_{\mathbf{b}}\mathbf{,}\mathbf{ }{\mathbf{P}}_{\mathbf{c}}$

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 

Step 2:

Now we introduce additional variables ${\mathbf{D}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathbf{D}}_{\mathbf{2}}$ to get the productions into the normal form of CNF:

We get the final grammar:

Now it is in CNF.