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