11
$\begingroup$

CFG here stands for context-free grammar. I understand that:

  1. Deciding whether a CFG $G$ is ambiguous is undecidable.

  2. Deciding whether a CFL $L$ is inherently ambiguous is undecidable.

My question is:

Is there an algorithm $A$ to remove ambiguity from an ambiguous grammar $G$ of a NOT inherently ambiguous language $L(G)$?

To specify the behavior of $A$ more precisely, $A$ operates on $G$ and:

  1. If $L(G)$ is not inherently ambiguous, $A$ outputs a CFG $G'$ so that $G'$ is not ambiguous and $L(G') = L(G)$.

  2. If $L(G)$ is inherently ambiguous, $A$ outputs something arbitrarily.

Is this problem known to be undecidable, or still open? Any comments and links are welcome. Thanks.

Improve this question
$\endgroup$
3
  • $\begingroup$ If $L(G)$ is inherently ambiguous, is it acceptable to run forever, rather than outputting something arbitrary? $\endgroup$
    – Max
    Dec 28, 2012 at 22:40
  • $\begingroup$ @Max I think that's fine. And that seems to relax the problem, but can you prove it? $\endgroup$
    – Cyker
    Dec 30, 2012 at 5:26
  • $\begingroup$ This isn't an answer, but it could be a step in the right direction. Given a pair $(M,x)$ consisting of a TM and an input, it is possible to construct a CFG $G_{M,x}$ such that the language of $G_{M,x}$ excludes exactly the strings that are accepting computation histories of $M$ on $x$ (see any textbook proof that $ALL_{CFG}$ is undecidable). Note that $L(G_{M,x})$ is not inherently ambiguous, so applying a hypothetical decider for your problem yields an unambiguous CFG for $L(G_{M,x})$. Thus, an algorithm deciding whether a given unambiguous CFG accepts all inputs would yield a contradiction. $\endgroup$
    – Mikhail Rudoy
    Nov 22, 2017 at 2:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.