0

There is a theorem related to CFGs that " There exists no algorithm which can decide whether a grammar is ambiguous or not."

I have developed an algorithm which can decide the ambiguity of a cfg.

But the proof of the above theorem is based on Post Correspondence Problem (PCP). Please tell me if I publish the algorithm would that mean that this theorem is not correct.

Note: Please also post some ambiguous cfgs. I want to test my algo.

user112822
  • 79
  • 1
  • 1
  • Strictly speaking, the answer to your question is "no", since having a result published is no guarantee that the result is true. Snarkiness aside, though, if you present an algorithm that decides whether a CFG is ambiguous and your presentation contained a valid proof that the algorithm was correct, then yes, it would contradict the proof that CFG ambiguity was undecidable, so that proof would be incorrect. Of course, that wouldn't necessarily cast doubt on the undecidability of the PCP. – Rick Decker Dec 03 '13 at 15:08
  • Look at the proof that links the PCP into ambiguity. That will show how to find grammars to test your algorithm. Just perform the construction on an instance of PCP and use your algorithm to find whether the resulting grammar is ambiguous. You can find PCP examples on the web. – Hendrik Jan Dec 28 '13 at 13:39

1 Answers1

2

A good heuristic is: "If you think you have disproved previously proved result X, you are more likely wrong."

I am not sure how many people have worked on PCP over the years. It is most likely a lot, and they have most likely been competent computer scientists and mathematicians.

I would tend to trust a group like that to reason mathematically, more than I would trust myself.

Your algorithm is most likely wrong (there is a probability $\varepsilon > 0 $ that it is correct and all these mathematicians are wrong, for an almost arbitrarily small $\varepsilon$).

It is well known that the grammar of the programming language C++ is ambiguous when expressed as a CFG.

Also, try to present a counterexample for your algorithm. You designed it, you should know when it breaks.

Kile Kasmir Asmussen
  • 817
  • 5
  • 11