**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