# 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?

1. D. G. Cantor, On The Ambiguity Problem of Backus Systems.

2. R. W. Floyd, On ambiguity in phrase structure languages.