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.
$\begingroup$
$\endgroup$
-
$\begingroup$ What makes you think that $\{\langle G \rangle \mid L(G) \neq \Sigma^\ast\}$ is not recursively enumerable? $\endgroup$ – ttnick Dec 16 '18 at 22:48
$\begingroup$
$\endgroup$
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:
- 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)$).
- Convert $G$ in Chomsky normal form $G'$.
- 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.
-
$\begingroup$ Not $A^C$. It is $A^C \cap \{\langle G \rangle \}$ $\endgroup$ – John L. Dec 16 '18 at 23:11
-
$\begingroup$ 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$. $\endgroup$ – ttnick Dec 16 '18 at 23:22
-
$\begingroup$ 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"? $\endgroup$ – John L. Dec 17 '18 at 1:17
-
1$\begingroup$ It is certainly worth a mention, so I added this step to the procedure. $\endgroup$ – ttnick Dec 17 '18 at 14:02
