Determining Ambiguity in Context Free Grammars

To determine if a context free grammar is ambiguous is undecidable (there is no algorithm which will correctly say "yes" or "no" in a finite time for all grammars). This doesn't mean there aren't classes of grammars where an answer is possible.

To prove a grammar ambiguous, you do as you outline: Find a string with two parses. To prove it unambiguous is harder: You have to prove the above isn't possible. It is known that the $LL(k)$ and $LR(k)$ grammars are unambiguous, and for $k = 1$ the conditions are relatively easy to check.

let $G= (V,T,P,S)$, where $P$ are:

• $S\to S(E)|E$
• $E\to (S)E|0|1|ϵ$

Now consider a string $w \in L(G)$

$w = (0)(0)()1$

Construct Left Derivation

$S\to E\to (S)E\to (0)E\to (0)(S)E\to (0)(0)E\to (0)(0)(S)E\to (0)(0)(ϵ)E\to (0)(0)()E\to (0)(0)()1.$

Construct Right Derivation $S\to E\to (S)E\to (S)(S)E\to (S)(S)(S)E\to (S)(S)(S)1\to (S)(S)(ϵ)1\to (S)(S)()1\to (S)(0)()1\to (0)(0)()1.$

We were able to construct 2 distinct Derivations. Hence This Grammar is ambiguous.

"If a grammar produces at least 2 distinct parse tree or derivations, then the grammar is ambiguous."

If CFG may produce more than one parse tree for the same input string then the grammar is said to be ambiguous. Very easily we can able to identify that. (i.e) when the same non-terminal appears twice on a right hand side of the production then it has the ambiguity problem. The general form of the ambiguous grammar is: S -> α S β S γ | α1| α2 | α3 | …. |αn this production has an ambiguity problem because S are present twice on the right hand side of the production. Where α,β and γ are some string. Example E -> E + E | E * E | (E) | id