Algorithm for CFG to CNF conversion

Some important things to note are -

• For a given grammar there can be more than one CNF.

• CNF produces the same language as generated by CFG.

• CNF is used to proproccess the many algorithms for CFG like CYK, etc.

Step 1. Eliminate start symbol from RHS. create new production for the same if required.

So $\rightarrow$ S. where so is new start symbol.

Step 2. Eliminate null, unit and useless productions.

Step 3. Eliminate terminals from RHS if they exist with other terminals or non-terminal.

eg. X $\rightarrow$ XY can be expressed as

X $\rightarrow$ ZY

Z $\rightarrow$ X

Step 4. Eliminate RHS with more than two non-terminals.

eg. X $\rightarrow$ XYZ can be expressed as

X $\rightarrow$ PZ

P $\rightarrow$ XY