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

I have a BNF defined as follow:

<S> -> 0
<S> -> 1
<S> -> <S><S>

I think this grammar is not ambiguous, but the solution was 'yes'. Any idea?
The book solution is odd to me, because I think it is the same as the one above.

<S>-> 0|1|<S><S>


share|cite|improve this question
You give two times the same grammar. An unambiguous grammar for the same language is $S \rightarrow 0S \mid 1S \mid 0 \mid 1$, for instance. – Raphael Feb 17 '11 at 11:05
up vote 10 down vote accepted

A general technique to check for ambiguity is this. Transform the grammar in an equation system:

$S(x) = S(x)^2 + 2x$

Solving for $S(x)$ yields $S(x) = \frac{1}{2}(1 - \sqrt{1 - 8x})$ which is the ordinary generating function enumerating the grammar's left-derivation trees.

The generated language is $\{0,1\}^+$ which has the generating function $\frac{1}{1-2x} - 1$. This is obviously different from the above, therefore there are more left-derivation trees (for words of length $n$) than words (of length $n$).

This technique goes back to Chomsky and Schützenberger, 1963.

share|cite|improve this answer
Interesting! Never heard of this approach till now... +1. – Aryabhata Feb 17 '11 at 8:38
Yea, few have. Which is funny given how old it is. My advisor uses generating functions heavily and happily, so he teaches us such things. Note, though, that this approach can be arbitrarily hard to execute (solving the equation system and comparing the resulting functions). Computer algebra systems help a lot. – Raphael Feb 17 '11 at 8:42

Consider the following:

$S \to S S \to S S S \to 1 S S \to 1 1 S \to 1 1 1$

$S \to S S \to 1 S \to 1 S S \to 1 1 S\to 1 1 1$

share|cite|improve this answer
@Moron: Thanks! But how about the solution? I believe it could generate two distinct parse trees too. – Chan Feb 17 '11 at 7:57
@chan: The 'solution' just seems to be restating the grammar rules... Did you forget to copy something? – Aryabhata Feb 17 '11 at 8:01
@Moron: I copied it verbatim. It has two solutions, the other one is EBNF: <S> -> {0|1}(0|1). And this is not the first time I'm confused by my teacher's solution, he seemed very vague in explaining things. – Chan Feb 17 '11 at 8:07
Thanks both. So the solution must be $\{0, 1\}^+$, and it's impossible to write it in recursive from, right? – Chan Feb 17 '11 at 8:43
@Chan: No idea, it has been a long time for me... – Aryabhata Feb 17 '11 at 9:07

Consider that string = 000

1) S = S S = (S S) S = (0 0) 0 = 000

2) S = S S = S ( S S) = 0 (0 0 ) = 000

share|cite|improve this answer
If I read your non-standard notation correctly, 1) is a left-derivation and 2) a right-derivation. Hence, this is not a witness for the grammar being ambiguous. – Raphael Apr 25 '14 at 10:47

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.