World's most popular travel blog for travel bloggers.

# Explanation of Grammar Ambiguity

, ,
Problem Detail:

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

###### Answered By : Yuval Filmus

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)$.