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

		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, So
		
		S -> NA/MB
		A -> NO/MS/a
		N -> a
		M -> b
		O -> AA