<p><em>CFG</em> here stands for <em>context-free grammar</em>. I understand that:</p>

<ol>
<li><p>Deciding whether a CFG $G$ is ambiguous is undecidable.</p></li>
<li><p>Deciding whether a CFL $L$ is inherently ambiguous is undecidable. </p></li>
</ol>

<p>My question is:</p>

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

<p>To specify the behavior of $A$ more precisely, $A$ operates on $G$ and:</p>

<ol>
<li><p>If $L(G)$ is not inherently ambiguous, $A$ outputs a CFG $G'$ so that $G'$ is not ambiguous and $L(G') = L(G)$.</p></li>
<li><p>If $L(G)$ is inherently ambiguous, $A$ outputs something arbitrarily.</p></li>
</ol>

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

CC BY-SA 3.0
2012-12-28T22:40:07.490Z
If $L(G)$ is inherently ambiguous, is it acceptable to run forever, rather than outputting something arbitrary?
Max
CC BY-SA 3.0
2012-12-30T05:26:41.473Z
@Max I think that's fine. And that seems to relax the problem, but can you prove it?
Cyker
CC BY-SA 3.0
2017-11-22T02:21:28.203Z
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.
Mikhail Rudoy
<context-free><undecidability>
Eliminate ambiguity from CFG
Cyker
# Eliminate ambiguity from CFG

(Asked by: username_0 on 2012-12-23)

*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.

**Tags:** context-free, undecidability

> **Comments:**
> **username_1**: If $L(G)$ is inherently ambiguous, is it acceptable to run forever, rather than outputting something arbitrary?  
> **username_0**: @username_1 I think that's fine. And that seems to relax the problem, but can you prove it?  
> **username_2**: 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.  

---

## 0 answers

