+1 vote
24 views

Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$.

1. Show that $NECESSARY_{CFG}$ is Turing-recognizable.
2. Show that $NECESSARY_{CFG}$is undecidable.

edited | 24 views