Are there any examples of context-free grammars for which we simply do not know whether they are ambiguous? By examples I mean an actual specification for the grammar, not some kind of non-constructive existence proof with a counting argument or whatnot. To make things more clear, I should be able to write a parser for this grammar from the specification (this should exclude grammars that are somehow defined via constructions involving other undecidable problems).

I am not a specialist so I hope the previous paragraph makes what I mean clear enough. Otherwise please do let me know if you think I am not being clear enough.

Another point: coming up with a random grammar specification on the spot and claiming its ambiguity is unknown because no one has tried to figure it out does not count. I guess I am really looking for known open problems in this area.

  • 1
    $\begingroup$ You have succumbed to a common misconception: undecidability does not imply that a single instance must be "unclear". See also here. Duplicate? $\endgroup$ – Raphael Jan 9 '18 at 23:05
  • $\begingroup$ I see. So it turns out my question is equivalent to asking for specific examples of Turing machines whose halting we do not know? $\endgroup$ – Tob Ernack Jan 9 '18 at 23:11
  • $\begingroup$ I suppose that makes sense because of the reductions to the Post correspondence problem which itself reduces to the halting problem. $\endgroup$ – Tob Ernack Jan 9 '18 at 23:16
  • $\begingroup$ And for the fallacy you describe in the linked question: in your answer you state that one of the algorithms that always outputs Yes or always outputs No will correctly decide for a specific instance of the problem. So is your point that the problem is decidable because such an algorithm exists, even if we don't know which one is actually correct? $\endgroup$ – Tob Ernack Jan 9 '18 at 23:26
  • 1
    $\begingroup$ Thank you for your reply. So when I say "we cannot even prove that the ambiguity problem is undecidable for this particular grammar", I am wrong because we can, and the answer is "it is decidable". In that case, I will retract this claim, but my question still stands: I am interested in particular cases where CFG ambiguity has not been determined, as far as public research knowledge goes. $\endgroup$ – Tob Ernack Jan 9 '18 at 23:50

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.