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
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:
The uniform version tells you it's impossible to solve the problem for all instances.
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
T? (Note that both
T have an infinite cardinality.)