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

  • $\begingroup$ 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$) $\endgroup$
    – Shaull
    Feb 21, 2013 at 5:59
  • $\begingroup$ 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). $\endgroup$
    – Cyker
    Feb 22, 2013 at 10:05
  • $\begingroup$ They are both countable (there are only countably many CFGs, and $T$ is infinite). Is that what you mean? $\endgroup$
    – Shaull
    Feb 22, 2013 at 10:08
  • $\begingroup$ 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...) $\endgroup$
    – Cyker
    Feb 22, 2013 at 10:10
  • 1
    $\begingroup$ @shaull ok, yes, promise problems 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. $\endgroup$
    – vzn
    Feb 25, 2013 at 16:19


Your Answer

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

Browse other questions tagged or ask your own question.