0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Have you looked at the definition of CNF and the conversion method (you got the first steps from somewhere, I assume)? $\endgroup$
    – Raphael
    Commented Nov 9, 2013 at 15:22

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I was just going to give the answer, but your explanation probably serves them better. +1 $\endgroup$
    – Brad Allred
    Commented Nov 9, 2013 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.