4
$\begingroup$

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

  • 0
    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.2011-02-17

4 Answers 4

13

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

  • 3
    Interesting! Never heard of this approach till now... +1.2011-02-17
  • 1
    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.2011-02-17
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$

  • 0
    @Moron: Thanks! But how about the solution? I believe it could generate two distinct parse trees too.2011-02-17
  • 0
    @chan: The 'solution' just seems to be restating the grammar rules... Did you forget to copy something?2011-02-17
  • 0
    @Moron: I copied it verbatim. It has two solutions, the other one is EBNF: ` -> {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.2011-02-17
  • 0
    Thanks both. So the solution must be $\{0, 1\}^+$, and it's impossible to write it in recursive from, right?2011-02-17
  • 0
    @Chan: No idea, it has been a long time for me...2011-02-17
  • 0
    What do you mean by "recursive form"? There are trivial unambiguous grammars for $\{0,1\}^+$, if that is your concern.2011-02-17
  • 0
    @Raphael: sorry for late reply. By recursive form, I mean the sentential from can be generated using either left or right most derivation.2011-02-18
  • 0
    That is possible with ambiguous grammars, even in more ways than one.2011-02-18
0

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

  • 0
    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.2014-04-25
0

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