# Michael Sipser Edition 3 Exercise 4 Question 28 (Page No. 212)

27 views
Let $C = \{ \langle G, x \rangle \mid \text{G is a CFG$x$is a substring of some$y \in L(G)$}\}$. Show that $C$ is decidable. (Hint: An elegant solution to this problem uses the decider for $E_{CFG}$.)

## Related questions

1
75 views
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly$k$strings where$k \geq 0$or$k = \infty$}\}$. Show that $C_{CFG}$ is decidable.
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.