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.

$\endgroup$
  • $\begingroup$ If $L(G)$ is inherently ambiguous, is it acceptable to run forever, rather than outputting something arbitrary? $\endgroup$ – Max Dec 28 '12 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 '12 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 '17 at 2:21

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.