Hardness of ambiguity/non-ambiguity for context-free grammars A grammar is ambiguous if at least one of the words in the
language it defines can be parsed in more than one way. A simple example of an ambiguous grammar
$$
   E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ 1 \ |\ ...
$$
because the string 1+2*3 can be parsed as (1+2)*3 and 1+(2*3).  For
context free grammars (CFGs) ambiguity is not decidable [1, 2]. This implies that non-ambiguity is also not decidable. Moreover, at least one of ambiguity and
non-ambiguity cannot even be recursively enumerable, for otherwise
ambiguity of a given CFG $G$ could be decided by running the
enumeration of ambiguity and non-ambiguity together and seeing which
one contains $G$ (and one of them must).

So which problem is harder in this sense? Ambiguity or non-ambiguity?


D. G. Cantor, On The Ambiguity Problem of Backus Systems.
R. W. Floyd, On ambiguity in phrase structure languages.
Ambiguous grammars can be enumerated, since each ambiguous grammar has a proof of ambiguity, namely a word with two different parses.