I have a BNF defined as follow:
-> 0 -> 1 ->
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.
-> 0|1|
Thanks,
Chan
I have a BNF defined as follow:
-> 0 -> 1 ->
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.
-> 0|1|
Thanks,
Chan
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).
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$
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
You may be write LHS(left hand side) of your BNF and RHS(right hand side) like above cmt to solve that. After have LHS and RHS of your BNF, we will compare two of these, if there are no different between of these => Your BNF not ambigous and vice versa. Good luck :D