0
$\begingroup$

So I've been struggling for the past hour with $G=(\{S\},\{a,b\},P,S)$ with productions $S\to aaSb | abSbS | \varepsilon$. I need to prove whether this grammar is ambiguous or not. Thus far I think it is ambiguous, possibly cuz of abSbS, but not sure (mainly since I have no idea how to prove it's not) . Can anyone help? I tried several words to no avail.

$\endgroup$
  • 2
    $\begingroup$ Try to use the definition of ambiguous. $\endgroup$ – Yuval Filmus Feb 6 '16 at 14:31
  • 1
    $\begingroup$ Much helpful, so advice. Not like I've been trying to find a word that would prove it's ambiguous for the past hour. $\endgroup$ – Bumblebee Feb 6 '16 at 14:40
  • 3
    $\begingroup$ To show that the grammar is ambiguous, you need to find a word with two different derivation trees. If you understand all of this, just do that. Don't ask others to do it for you. $\endgroup$ – Yuval Filmus Feb 6 '16 at 16:33
  • 1
    $\begingroup$ @tisasecret A grammar this size is likely to exhibit ambiguity for some small world, or not at all. So trying all the words ordered by length should work in under an hour. $\endgroup$ – Raphael Feb 6 '16 at 16:59
  • $\begingroup$ @YuvalFilmus are you sure about $abbaab$? I tried to solve that, it looks unambiguous $\endgroup$ – 3SAT Feb 6 '16 at 21:48
2
$\begingroup$

Here is an outline of a parsing procedure. To prove that the grammar is unambiguous, you have to show that it works (parses the string), and furthermore that the parsing tree it produces is the unique one generating the string. If this question came up in the context of a course on compilers, then you should have learned the necessary tools.

The parser is a DPDA. The stack starts initialized with S, and then works according to the following rules, reading the input from left to right.

  1. If the top-of-stack is S:

    • If the string starts aa, replace S with AS (S on top).
    • If the string starts ab, replace S with BS.
    • If the string starts and ends a, reject.
    • If the string ends, accept.
    • If the string starts b, delete S and process b again.
  2. If the top-of-stack is A:

    • If the string starts b, delete A.
    • Otherwise, reject.
  3. If the top-of-stack is B:

    • If the string starts b, replace B with S.
    • Otherwise, reject.

(Unless explicitly stated, the automaton consumes the characters it reads from the string.) At the end of parsing, the automaton rejects unless the stack is empty.

I'll let you figure out how to construct the actual parse tree. You'll also have to figure out how to prove that this parsing tree is the unique one (if it is indeed the case).

$\endgroup$
  • $\begingroup$ "The parser is a DPDA." -- that's crucial, but not sufficient. The automaton has to "implement" the exact grammar (whatever that means) if this is supposed to show anything. $\endgroup$ – Raphael Feb 7 '16 at 17:46
  • $\begingroup$ @Raphael This is not intended to be a complete proof – after all it's not my exercise. If you want you can spend some time fleshing it out. $\endgroup$ – Yuval Filmus Feb 7 '16 at 20:38
  • 1
    $\begingroup$ I don't think this leads to a proof at all. Not because of the automaton you sketch, or what follows, but because of the logic of it. The problem is that this "technique" can be used to "prove" that ambiguous grammars are unambiguous by giving a deterministic automaton for the same language. How would you allow one automaton but not another for the proof? $\endgroup$ – Raphael Feb 8 '16 at 7:16
1
$\begingroup$

To show that this CFG is unambiguous you can try convert it into a LL(1) (preserving ambiguity). Then, if you can do it, the original CFG will be unambiguous too (o course, if you cannot, you won't show anything about ambiguity). If you use left-factoring on S → aaSb|abSbS|ε you get: S → aT|ε, T → aSb|bSbS. Show that this CFG is LL(1) and you will get your prove (because all LL(1) grammars are unambiguous and left-factoring preserves ambiguity).

$\endgroup$
  • $\begingroup$ LL(2) grammars are also unambiguous. $\endgroup$ – rici May 31 '18 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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