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

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.

• What makes you think that $\{\langle G \rangle \mid L(G) \neq \Sigma^\ast\}$ is not recursively enumerable? – ttnick Dec 16 '18 at 22:48

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.

• Not $A^C$. It is $A^C \cap \{\langle G \rangle \}$ – Apass.Jack Dec 16 '18 at 23:11
• I don't think that makes a difference. One can always assume that any string $x$ is an encoding of a context-free grammar. In case of doubt just set $x = \langle S \to \varepsilon \rangle$. – ttnick Dec 16 '18 at 23:22
• I meant you might be supposed to show or at least mention the set of all encodings of context-free grammar is decidable. "any string x is an encoding of a context-free grammar"? – Apass.Jack Dec 17 '18 at 1:17
• It is certainly worth a mention, so I added this step to the procedure. – ttnick Dec 17 '18 at 14:02