Is the set of context free grammars that generate all words in co-RE?

Question

Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.

Answer 1

For $A = \{\langle G \rangle \mid L(G) \neq \Sigma^\ast\}$ this procedure, returns "yes" iff there is a word $w \notin L(G)$ for a given grammar encoding $\langle G \rangle$ and never halts otherwise:

1. Assume the input encodes a context-free grammar $G$. Otherwise, accept the input if it is not an encoding of a context-free grammar. (Note, however, that we can always assume that every string encodes some dummy grammar, e.g. $(\{S\}, \{a\}, \{S \to \varepsilon\}, S)$).
2. Convert $G$ in Chomsky normal form $G'$.
3. For each $w \in \Sigma^\ast$:
   Check whether there exists a derivation in $G'$. Note that for a grammar in Chomsky normal form a derivation of a word $w$ has length $ \leq 2 |w|$, so you only have to check finitely many for each word. If such an derivation does not exists, return "yes", otherwise continue with next word.

Thus, $A$ is recursively enumerable and $A^C = \{\langle G \rangle \mid L(G) = \Sigma^\ast\}$ is co-RE.