# Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous

Question: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous.

The CFG is as follows. $$G = (V:=\{E,T,F\}, \Sigma:=\{+, \times,(,),x\},R,E\})$$

where $$R$$ consists of 6 rules:

$$E\rightarrow E+T ~|~ T~~~~~~ T\rightarrow T\times F|F~~~~~~ F\rightarrow (E) | x$$

My thoughts: I think we should start by showing each string $$s$$ in language has a unique derivation by strong induction on the length of $$s$$, but not sure how to proceed. Could you please help?

Many thanks!

• "Removing left recursion cannot introduce ambiguity. This kind of transformation preserves ambiguity. If the CFG is already ambiguous, the result will be ambiguous too, and if the original is not, the resulting neither" says Andres at here Commented Jul 21, 2022 at 2:07

So can we have two derivation trees that start with the productions $$F\to (E)$$ and $$F\to x$$ and derive the same string. Obviously not. The same should be checked for the pair $$E\to E+T$$, $$E\to T$$ and the pair $$T\to T\times F$$, $$T\to F$$.