1
$\begingroup$

I tried to solve if a grammar is ambiguous or not. I know that I have to find a word that can be generate by two different leftmost derivations. Is there any algorithm to find a word that, if the grammar is ambiguous, can be generated by two different trees? This question is different.

$\endgroup$
  • $\begingroup$ Possible duplicate of Ambiguous context free $\endgroup$ – rici Oct 5 at 15:01
  • $\begingroup$ @rici, I'm not quite understanding how it is a duplicate; can you elaborate? $\endgroup$ – D.W. Oct 5 at 16:02
  • $\begingroup$ @D.w.: ok, how about this one: cs.stackexchange.com/questions/84475/…. I just gave a hard time believing that there isn't a duplicate somewhere on this site. (I was rushing this morning, sorry. But the answer to the Q I suggested does include "it is undecidable whether a given CF grammar is ambiguous (1962-63, Cantor - Floyd - Chomsky and Schutzenberger)", which is certainly the answer to this Q. $\endgroup$ – rici Oct 5 at 20:42
  • $\begingroup$ The algorithm is to enumerate all parse trees and to check whether there is a word generated twice. If your grammar is ambiguous then the algorithm is guaranteed to halt. $\endgroup$ – Yuval Filmus Oct 5 at 22:48
  • $\begingroup$ Cool. It looks like this post asks two questions: (1) can we determine whether a grammar is ambiguous or not; (2) if we know that the grammar is ambiguous, how can we find a word that can be generated by two different trees? The first is a dup of cs.stackexchange.com/questions/84475 as rici says. The second is answered by Yuval. edoardott, can you edit your post to focus only on the second question, so that we can answer it rather than marking it as a duplicate of that other question? $\endgroup$ – D.W. Oct 6 at 0:09

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.