# conversion of this grammar to CNF

My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$

after removing lambda productions: $S\to SS, S\to (S), S\to(), S\to S$

after removing unit productions: $S\to SS, S\to (S), S\to()$

I got upto this point. Do not know how this grammar will be in CNF coz I am not sure if using () makes the grammar illegal. Need help how to proceed and make this grammar in CNF?

• Have you looked at the definition of CNF and the conversion method (you got the first steps from somewhere, I assume)? – Raphael Nov 9 '13 at 15:22

## 1 Answer

Yes, the grammar you noww have is still illegal. For CFG you can only have two types of productions $A\to BC$ and $A\to a$ where $A,B,C$ are nonterminals (variables) and $a$ terminal.

It is best to add additional variables that introduce the brackets $A\to ($ and $B\to )$. Now you can use $S\to AB$ instead of your production $S\to ()$.

Finally, try to get rid of $S\to (S)$. It is too long and contains both terminals and nonterminals on the right side.

• I was just going to give the answer, but your explanation probably serves them better. +1 – Brad Allred Nov 9 '13 at 18:45