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$ 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

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.

| cite | improve this answer | |
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.