2
$\begingroup$

Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).

$\endgroup$
  • 1
    $\begingroup$ Are you asking whether it is decidable to check whether a given context-free grammar generates an inherently ambiguous language? If so, then the answer is no: it is undecidable. See this answer: cstheory.stackexchange.com/a/19116/40. $\endgroup$ – Yuval Filmus Jul 2 '16 at 19:27
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jul 2 '16 at 19:43
  • $\begingroup$ I am asking for whether is there any Halting Turing machine available for converting an ambiguous grammar into an unambiguous grammar. If yes then the problem of converting an ambiguous grammar into an unambiguous grammar is computable (or decidable). $\endgroup$ – Krunal Jul 3 '16 at 6:11
  • $\begingroup$ Note that deciding ambiguity is not computable so chances are slim. $\endgroup$ – Raphael Jul 3 '16 at 9:54
0
$\begingroup$

I assume that question is about derivation, otherwise the outcome does not change, but please read Yuval's comment for further details.

No it is not computable in the domain of your choice. There are inherently ambigous grammars, which are subset of context-free grammars. For the subset without inherently ambigous ones it is computable.

I like to point to thesis about ambiguous grammars, which is consistent with what I wrote, contains the same proof as TCS topic.

Since the problem of finding out whether grammar is inherently ambiguous is undecidable then you cannot build halting Turing Machine for such task. And yes, if you could built one it would be decidable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not sure this is correct - how do you construct an equivalent unambiguous grammar, given that one exists? $\endgroup$ – Yuval Filmus Jul 3 '16 at 6:37
  • $\begingroup$ Seconded. Deciding ambiguity is not computable so this should be interesting. $\endgroup$ – Raphael Jul 3 '16 at 9:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.