I have this grammar:

$S\rightarrow SS |S \rightarrow(S)|S\rightarrow\epsilon $

Now this grammar generates the set of balanced parentheses. But this grammar is ambiguous. I am trying to find an unambiguous grammar for this language but all in vain. This has led me to believe that the language is inherently ambiguous. Am I true? If not please provide an unambiguous grammar for this language.

  • 2
    $\begingroup$ Since a DPDA is almost trivial, the language is clearly not inherently ambiguous. And, from this DPDA, you also get a grammar using the standard construction. $\endgroup$ – Raphael Nov 6 '17 at 6:45

$$S \rightarrow (S)S$$ $$S \rightarrow \epsilon$$

Generalising this to other Dyck languages is left as an exercise.

| cite | improve this answer | |

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