# Explanation of Grammar Ambiguity

Consider now the grammar G

S -> (S + S)
S -> (S * S)
S -> a

Is it ambiguous?

Answer: No because there are disambiguating parentheses and so no left or right recursion.

Can someone explain how the parentheses are disambiguating. I could understand if they were "[" and "(".

Appreciate the help

• Crossposted on math.se math.stackexchange.com/questions/1759611/… – Ran G. Apr 28 '16 at 18:16
• Yeah, sorry I'm fairly new is double posting allowed? I thought people here might be better at answering – Daniel Apr 28 '16 at 18:45
• Cross-posting (posting on several sites at once) is frowned upon. A moderator will eventually merge both questions. – Yuval Filmus Apr 28 '16 at 20:46
• Note that the ambiguity of the related grammar $S\to S+S\mid S*S \mid a$ is not caused by the two operators. Even $S\to S+S\mid a$ is ambiguous: we do not know how $a+a+a$ was derived. Brackets help to distinguish $((a+a)+a)$ from $(a+(a+a))$. See the answer by @YuvalFilmus for full details. – Hendrik Jan Apr 29 '16 at 2:48

A grammar $G$ is non-amgibuous if every word in $L(G)$ has a unique parse tree. The simplest way to prove that your grammar non-ambiguous is to prove that $L(S + S),L(S * S),L(a)$ are all distinct (here $L(\alpha)$ is the set of all words that can be generated from the sentential expression $\alpha$); given this, an easy induction shows that $L(G)$ is non-ambiguous.
It is clear that $L(S + S)$ and $L(S * S)$ are disjoint from $L(a)$. To prove that $L(S + S)$ and $L(S * S)$ themselves are disjoint, you can prove by induction that each word generated by $S$ is either $a$ or of the form $(w)$, where $w$ is a well-parenthesized expression (parenthesis close each other correctly), and this gives you a rule for identifying the first and the second $S$ in word generated by $L(S + S)$ and $L(S * S)$; the symbol in between determines whether the word belongs to $L(S + S)$ or to $L(S * S)$.