# Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have?

For example, consider the following Grammar G:

$S \rightarrow S(E)|E$

$E \rightarrow (S)E|0|1|\epsilon$

My guess is that this grammar is not ambiguous, because of the parentheses I could not make an equivalent strings with distinct parse trees. I could have easily made a mistake since I am new to this. What are some common enumeration techniques for attempting to construct the same string with different parse trees?

1. How can I know that I am right or wrong?
2. What are common attributes of ambiguous grammars?
3. How could I prove this to myself intuitively?
4. How could I prove this with formal mathematics?
-
See an answer of mine over Computer Science. – Raphael Feb 9 '13 at 13:50
This is strongly related to this thread: math.stackexchange.com/questions/17735/… – eff_it Nov 25 '13 at 4:02
@Raphael nice answer there in the link! – Suhail Apr 6 at 12:25

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.

-
in case anyone wants to know why the problem is undecidable check this out cstheory.stackexchange.com/questions/4352/… – kiyarash Apr 27 at 18:50
although it is not easy to understand – kiyarash Apr 27 at 18:52

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."

-
An even simpler ambiguous string is $()$. – Peter Taylor Dec 2 '13 at 8:05