0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by Evil, David Richerby, Rick Decker, Yuval Filmus, Juho Nov 10 '17 at 22:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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
4
$\begingroup$

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

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

$\endgroup$

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