Is this BNF grammar ambiguous?

Question

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>

Thanks,
Chan

Answer 1

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 (PDF).

Answer 2

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$

Answer 3

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