Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
If $L(G)$ is inherently ambiguous, is it acceptable to run forever, rather than outputting something arbitrary? – Max Dec 28 '12 at 22:40
@Max I think that's fine. And that seems to relax the problem, but can you prove it? – cyker Dec 30 '12 at 5:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.