Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|cite|improve this question
See an answer of mine over Computer Science. – Raphael Feb 9 '13 at 13:50
This is strongly related to this thread:… – eff_it Nov 25 '13 at 4:02
@Raphael nice answer there in the link! – Sнаđошƒаӽ Apr 6 '15 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.

share|cite|improve this answer
in case anyone wants to know why the problem is undecidable check this out… – kiyarash Apr 27 '15 at 18:50
although it is not easy to understand – kiyarash Apr 27 '15 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."

share|cite|improve this answer
An even simpler ambiguous string is $()$. – Peter Taylor Dec 2 '13 at 8:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.