# Proving the grammar S → SS+ | SS∗ | a is unambiguous

Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a* generated by this grammar.

Is this grammar unambiguous?

I have browsed the Internet and I have found that there is no standard procedure for proving if a grammar is unambiguous or not. But sometimes induction on length of the string or maybe length of the derivations works. I think in this question I can do something via length of sentential forms but I am not sure if its rigorous or not.

My approach: induction on length of sentential forms

Base case: length=1 then it has to be S -> a hence unambiguous.
Induction step: for length <= n assume all sentential forms are unambiguous. Consider a sentential form ww'. So here w can be either S or a. If a then done since unique derivation else if S then only possibility is that there has to be SS+ or SS* hence we know S produces these unambiguously and the rest is unambiguous by hypothesis hence proved.

This seems more of a cyclic argument to me so I would be glad if someone could help me out.

By the way, what is the language generated by a grammar?

In this case, I think that it's the language that does postfix operation on addition and multiplication that is being described here. But how do we generalise for grammars?

– D.W.
Feb 4 at 22:00
• Yes, the language consists of reversed Polish notations where each number is denoted by the single character "a". Feb 7 at 6:51
• I can derive aa in two ways. Feb 7 at 7:10
• I see… * and + are used as actual symbols instead of part of the grammar. Feb 7 at 7:12
• "there has to be SS+ or SS* hence we know S produces these unambiguously." Which S produces what? Had you specified clearly what are they referring to, you will see there is some significant gap. Feb 7 at 10:52

### $$L(G)$$ is the set of all p-expressions

Let an operator mean either $$+$$ or $$*$$. In order to characterize the strings generated by $$G$$, we may observe the number of operators and the number of $$a$$'s in a string.

Call a string $$w$$ over alphabet $$\{a, +, *\}$$ a p-expression if

• $$w$$ is non-empty, and
• there are at least as many operators as $$a$$'s in each proper suffix of $$w$$ while there are one less operators than $$a$$'s in $$w$$. (In particular, $$w$$ ends with an operator and starts with two $$a$$'s unless $$w=a$$.)

Claim: $$L(G)$$ is the set of all p-expressions.
Proof: Use structural induction. This is an easy exercise for the readers.

### $$G$$ is unambiguous

Proof: Let us show that $$w\in L(G)$$ has a unique parse tree using induction on $$|w|$$.

• Base case, $$|w|=1$$. Then $$w$$ must be $$a$$. $$S\to a$$ is the only derivation for $$w$$.
• As induction hypothesis, assume the proposition is true for $$|w|\le n$$.
Let $$|w|=n+1$$. WLOG, suppose $$w$$ ends with $$+$$. So the first step in the derivation for $$w$$ must be $$S\to SS+.$$
Let $$w_1$$ be the string produce by the first $$S$$ on the right hand side and $$w_2$$ be the string produced by the second $$S$$ so that $$w=w_1w_2+$$. Note that $$w_1, w_2\in L(G)$$.
Scanning $$w_1w_2+$$ from right to left character by character, let us track the difference of the number of operators and the number of $$a$$'s scanned. The claim above implies the last scanned character of $$w_2$$ must be the character at which that difference have dropped to 0 for the first time.
So $$w_2$$ is determined uniquely by $$w$$. Hence $$w_1$$ is also determined uniquely by $$w$$.
By induction hypothesis, there is a unique parse tree for $$w_1$$ and for $$w_2$$. Hence, there is a unique parse tree for $$w$$. $$\quad\checkmark$$

### Inspect $$G$$ reversed

Here is another way to show $$G$$ is unambiguous, which may appear simpler for readers with more experience.

Let $$G^r$$ be $$G$$ with production rules reversed, i.e., $$G^r=(\{a,+, *\}, \{S\}, \{S\to +SS, S\to *SS, s\to a\}, \{S\}).$$ It is easy to see that $$G$$ is unambiguous iff $$G^r$$ is unambiguous.

With some simple routine computation, we can obtain the $$LL(1)$$ parsing-table of $$G^r$$, $$\begin{array} {|c|c|c|c|}\hline &{\\\} &+ & * & a \\\hline S & &S\to +SS &S\to *SS & S\to a \\\hline \end{array}$$ As an $$LL(1)$$ grammar, $$G^r$$ is unambiguous. Hence, $$G$$ is ambiguous as well.

More generally, we can prove that a context-free grammar is unambiguous if all production rules end with different terminals.

### An exercise

Prove $$(\{0, 1,+, *\},$$ $$\{S, B\},$$ $$\{S\to SS+,$$ $$S\to SS*,$$ $$S\to B,$$ $$B\to 0B,$$ $$B\to 1B,$$ $$B\to 0,$$ $$B\to 1\},$$ $$\{S\})$$ is an unambiguous grammar.

• John, maybe the exercise has a typo? The nonterminal B is not generating. Feb 8 at 17:16
• @Tonita, thanks, updated. Feb 8 at 17:29

I would like to suggest another easy method to prove that the grammar $$G$$ is unambiguous. We can use the LR(0) parsing property to do so.

The language $$L(G)$$ is not prefix-free. If we add the endmarker $$\\\$$ to the language, thus introducing a new initial nonterminal $$S'$$ and the rule $$S'$$ $$\rightarrow$$ $$S$$ $$\\\$$ then the prefix property is satisfied. If the resulting grammar $$G'$$ is LR(0) then the initial grammar is necessarily unambiguous, otherwise we would get a parsing conflict for some word in $$L(G')$$. The LR(0)-property of $$G'$$ can be easily proven by constructing the corresponding finite state automaton.

Btw, this method does not provide a criterion of unambiguety, it gives only a sufficient condition. There are some unambiguous grammars that generate non-deterministic CFLs (the most famous example is the grammar generating even palindromes).

• Nice, with endmarker added $G$ does become LR(0) Feb 12 at 23:03