## CNF for Context Free Grammar

We have to check following form on a Context free grammar.

*All the productions should be of the form mentioned below:*

A -> BC or A -> a

### Advantages of CNF

- Length of each production is restricted
- Derivation tree or parse tree obtained from CNF is always binary tree
- Number of steps required to derive string of length |w| = (2|w| -1)
- It is easy to apply CYK algorithm

**Convert given grammar into CNF**

S -> bA/aB A -> bAA/aS/a Solution: Now we have to add new production: S -> NA/MB A -> NAA/MS/a N -> a M -> b Now combine NAA with either NA or AA, SoS -> NA/MB A -> NO/MS/a N -> a M -> b O -> AA