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.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Possible duplicate of Ambiguous context free $\endgroup$– riciCommented Oct 5, 2019 at 15:01
-
$\begingroup$ @rici, I'm not quite understanding how it is a duplicate; can you elaborate? $\endgroup$– D.W. ♦Commented Oct 5, 2019 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$– riciCommented Oct 5, 2019 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 FilmusCommented Oct 5, 2019 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. ♦Commented Oct 6, 2019 at 0:09
Add a comment
|