1
$\begingroup$

I know, it is not possible to decide whether a context free grammar is ambiguous or not. However, I am having a really hard time preparing for an upcoming exam in which I'll have to give a prove of un-/ambiguity for a given grammar.

Up until now,
the first thing I'd do is to look for a word (via try and error) which could be build up from more than just one tree. Despite the fact this takes quite some valuable exam-time, it hardly leads to a successful outcome for me. In addition I'm not really sure what to do if it actually is unambiguous.

What would be a proper way to prepare for such a problem without feeling like having to solve a pointless crossword puzzle you can not prepare for?

$\endgroup$
  • 1
    $\begingroup$ Do a few examples. There is no general problem solving strategy that always works. You just need enough experience. $\endgroup$ – Yuval Filmus Feb 13 '17 at 16:51
  • $\begingroup$ Any common strategies to keep back in mind? $\endgroup$ – cocoseis Feb 13 '17 at 18:39
  • 1
    $\begingroup$ You may look at ambiguity heuristics, a thesis comparing them. I am not sure whether these are practical for pen and paper method, but assuming short examples at the exam, maybe. $\endgroup$ – Evil Feb 14 '17 at 3:36
  • 1
    $\begingroup$ Since ambiguity is undecidable, you can't expect to find a method that always works. To prove that it's ambiguous, the easiest way is to provide two derivation trees for the same word. To prove that it's not ambiguous, you can prove that it's LL(k) or LR(k) for some k. $\endgroup$ – xavierm02 Feb 14 '17 at 13:26

Your Answer

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

Browse other questions tagged or ask your own question.