<p>The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version of this problem. That means, we just pick one CFG instead of considering all CFGs.</p>

<p>It's true (and trivial) that there is a Turing Machine <code>M</code> which can decide whether a fixed CFG <code>G</code> is ambiguous or not. <code>M</code> just needs to blindly output <code>True</code> or <code>False</code> according to the fact, i.e., whether <code>G</code> is actually ambiguous or not.</p>

<p>However, this is a non-constructive solution. It tells you the answer but doesn't provide with a proof. This is something like God's knowledge. </p>

<p>There is always a proof of ambiguity for any ambiguous CFG. This problem is recursively enumerable. But it's negation (i.e. proof of unambiguity) isn't. However, we can still find ways to prove unambiguity (for example, for very simple grammars like <code>S -&gt; a</code>).</p>

<p>The relationship between the uniform and non-uniform version of this problem is that:</p>

<ol>
<li><p>The uniform version tells you it's impossible to solve the problem for all instances.</p></li>
<li><p>The non-uniform version tries to tackle each instance based on it's unique characheristics. </p></li>
</ol>

<p>If we let the whole problem space (here it's the space of all instances of valid CFGs) be <code>S</code>, and the space of solvable instances (those come with a proof) w.r.t. ambiguity be <code>T</code>, what's the relationship between the size of <code>S</code> and <code>T</code>? (Note that both <code>S</code> and <code>T</code> have an infinite cardinality.)</p>

CC BY-SA 3.0
2013-02-21T05:59:05.947Z
So essentially, what you're asking is this: consider the TM that takes a grammar $G$, and in parallel checks all the proofs of unambiguity (if found - reject), and derivations that show that the grammar is ambiguous (if found - accept). What is the set of words on which this machine doesn't halt?

Clearly this set is undecidable. What kind of "relationship" are you looking for? (other than $T\subseteq S$)
Shaull
CC BY-SA 3.0
2013-02-22T10:05:33.603Z
To simplify the problem, it asks: How powerful are our techniques in solving undecidable problems. I'm looking for the relationship of the `size` of `S` (all valid CFGs) and `T` (all provably solvable CFGs). The TM you constructed needn't stop for some CFG as this is the uniform version of the problem (and thus undecidable).
Cyker
CC BY-SA 3.0
2013-02-22T10:08:08.767Z
They are both countable (there are only countably many CFGs, and $T$ is infinite). Is that what you mean?
Shaull
CC BY-SA 3.0
2013-02-22T10:10:41.197Z
Well that's true but too coarse-grained. Is there a more fine-grained measurement of countable sets to gauge the power of our techiques in solving undecidable problems? (This somehow reminds me of the set of all integers and that of all even integers...)
Cyker
CC BY-SA 3.0
2013-02-22T10:18:10.980Z
You could ask the following: Suppose we enumerate the CFG's in some *computable* order, then how is $T$ distributed along $S$? Is it very dense? (1 in every 5) or very sparse (1 in $2^n$)?

My guess is that current techniques are not even close to being able to answer it.
Shaull
CC BY-SA 3.0
2013-02-24T00:25:38.283Z
think this can be recast as a question about algorithms that correctly find answers to undecidable problems for a limited subset of cases and can figure out if the case is within the class, and answers (ie still halts with) "N/A" if the input is outside the class; have proposed calling them [quasialgorithms](http://cs.stackexchange.com/a/4866/699) and there is some knowledge in the area. however TCS is rather silent on the subject in general but it seems to be very significant/fundamental & highly worthy of further study/research.
vzn
CC BY-SA 3.0
2013-02-25T07:15:38.487Z
@vzn - what's the difference between "quasialgorithms", and promise problems for which the promise is decidable?
Shaull
CC BY-SA 3.0
2013-02-25T16:19:06.577Z
@shaull ok, yes, [promise problems](http://en.wikipedia.org/wiki/Promise_problem) are similar concept. promise problems are more general and do not require the promise to be decidable and also if the input is outside the promise set, promise algorithm output is undefined whereas for quasialgorithms its defined, and the machine returns "N/A". anyway there are apparently many nontrivial (fundamental?) properties waiting to be analyzed/discovered & the answer points out right away theres a natural partial order/hierarchy that doesnt seem to have been studied much.
vzn
CC BY-SA 3.0
2013-02-26T10:28:26.463Z
@Shaull The notion of promise problems provides a good way to reform the problem. Now the problem can be thought of as to expand the promise set as much as possible for a specific problem and then to ask what the largest size of the promise set can be. Here the problem is CFG ambiguity. But the idea applies generally.
Cyker
CC BY-SA 3.0
2013-02-26T10:45:26.120Z
@cyker- I think that saying "the largest size of the promise" is confusing. Perhaps it's better to ask how complicated the promise can be.

I think there is an interesting tradeoff here: on one hand, promise problems can make the problem must easier (up to trivial), and require nothing about the promise. On the other hand, quasialgorithms require a lot from the promise, thus making the problem not much easier. It is interesting to look at this scale (perhaps after we understand the quasialgorithm end-point better).
Shaull
<context-free><decidability>
Non-uniform CFG ambiguity decidability
Cyker
# Non-uniform CFG ambiguity decidability

(Asked by: username_0 on 2013-02-21)

The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version of this problem. That means, we just pick one CFG instead of considering all CFGs.

It's true (and trivial) that there is a Turing Machine `M` which can decide whether a fixed CFG `G` is ambiguous or not. `M` just needs to blindly output `True` or `False` according to the fact, i.e., whether `G` is actually ambiguous or not.

However, this is a non-constructive solution. It tells you the answer but doesn't provide with a proof. This is something like God's knowledge.

There is always a proof of ambiguity for any ambiguous CFG. This problem is recursively enumerable. But it's negation (i.e. proof of unambiguity) isn't. However, we can still find ways to prove unambiguity (for example, for very simple grammars like `S -> a`).

The relationship between the uniform and non-uniform version of this problem is that:

1. The uniform version tells you it's impossible to solve the problem for all instances.
2. The non-uniform version tries to tackle each instance based on it's unique characheristics.

If we let the whole problem space (here it's the space of all instances of valid CFGs) be `S`, and the space of solvable instances (those come with a proof) w.r.t. ambiguity be `T`, what's the relationship between the size of `S` and `T`? (Note that both `S` and `T` have an infinite cardinality.)

**Tags:** context-free, decidability
> **Comments:**
> **username_1**: So essentially, what you're asking is this: consider the TM that takes a grammar $G$, and in parallel checks all the proofs of unambiguity (if found - reject), and derivations that show that the grammar is ambiguous (if found - accept). What is the set of words on which this machine doesn't halt?  Clearly this set is undecidable. What kind of "relationship" are you looking for? (other than $T\subseteq S$)  
> **username_0**: To simplify the problem, it asks: How powerful are our techniques in solving undecidable problems. I'm looking for the relationship of the `size` of `S` (all valid CFGs) and `T` (all provably solvable CFGs). The TM you constructed needn't stop for some CFG as this is the uniform version of the problem (and thus undecidable).  
> **username_1**: They are both countable (there are only countably many CFGs, and $T$ is infinite). Is that what you mean?  
> **username_0**: Well that's true but too coarse-grained. Is there a more fine-grained measurement of countable sets to gauge the power of our techiques in solving undecidable problems? (This somehow reminds me of the set of all integers and that of all even integers...)  
> **username_1**: You could ask the following: Suppose we enumerate the CFG's in some *computable* order, then how is $T$ distributed along $S$? Is it very dense? (1 in every 5) or very sparse (1 in $2^n$)?  My guess is that current techniques are not even close to being able to answer it.  
> **username_2**: think this can be recast as a question about algorithms that correctly find answers to undecidable problems for a limited subset of cases and can figure out if the case is within the class, and answers (ie still halts with) "N/A" if the input is outside the class; have proposed calling them [quasialgorithms](http://cs.stackexchange.com/a/4866/699) and there is some knowledge in the area. however TCS is rather silent on the subject in general but it seems to be very significant/fundamental & highly worthy of further study/research.  
> **username_1**: @vzn - what's the difference between "quasialgorithms", and promise problems for which the promise is decidable?  
> **username_2**: @shaull ok, yes, [promise problems](http://en.wikipedia.org/wiki/Promise_problem) are similar concept. promise problems are more general and do not require the promise to be decidable and also if the input is outside the promise set, promise algorithm output is undefined whereas for quasialgorithms its defined, and the machine returns "N/A". anyway there are apparently many nontrivial (fundamental?) properties waiting to be analyzed/discovered & the answer points out right away theres a natural partial order/hierarchy that doesnt seem to have been studied much.  
> **username_0**: @Shaull The notion of promise problems provides a good way to reform the problem. Now the problem can be thought of as to expand the promise set as much as possible for a specific problem and then to ask what the largest size of the promise set can be. Here the problem is CFG ambiguity. But the idea applies generally.  
> **username_1**: @cyker- I think that saying "the largest size of the promise" is confusing. Perhaps it's better to ask how complicated the promise can be.  I think there is an interesting tradeoff here: on one hand, promise problems can make the problem must easier (up to trivial), and require nothing about the promise. On the other hand, quasialgorithms require a lot from the promise, thus making the problem not much easier. It is interesting to look at this scale (perhaps after we understand the quasialgorithm end-point better).  

---

## 0 answers

