How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?

I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is in $G$. Let $$\text{NECESSARY}_{\text{CFG}} =\{\langle G,A\rangle \mid G\text{ is a CFG and }A\text{ is a necessary variable in }G\}$$

• Show that $\text{NECESSARY}_{\text{CFG}}$ is Turing-recognizable.

• Show that $\text{NECESSARY}_{\text{CFG}}$ is undecidable.

This problem is a textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser.

This is my solution to part 1.

$D$ = On input $\langle G,A\rangle$:

• Create a CFG $H$ by eliminating the $A$ variable from the derivations of $G$.

• Create list of strings $w$ generated by grammar $G$.

• Create a decider for $\text{A}_{\text{CFG}}$ and check if each string of $w$ can also be generated by $H$.

• If $w$ strings cannot be generated by $H$ then accept.

• If some string cannot be generated by $H$ then reject.

For part 2, I don't have a solution. My thoughts would be to somehow reduce this to $\text{ALL}_{\text{CFG}}$ which is known to be undecidable.

An approach for the undecidability

Let $G$ be a context-free grammar. We can add to $G$ new context-free generation rules that employs new variables without using any variables in $G$ (except the initial variable of $G$) so that we end up with a grammar $H$ such that $H\in\text{ALL}_{\text{CFG}}$ and

$\quad$ $G\in\text{ALL}_{\text{CFG}}$ $\iff$ every new variable is not necessary in $H$.

Were $\text{NECESSARY}_{\text{CFG}}$ decidable, we could decide the right-hand side, and hence the left-hand side as well.
Some minor issues of your solutions

Your solution to part 1 is basically correct.

There are, apparently, some typos in step 4 and step 5. Step 5 , "... then reject" might be wrong since this procedural cannot end with rejecting when $L(G)$ contains infinitely many strings. It is unnecessary any way.

Here is a better way to write your solution.

Turing machine $D :=$ On input $\langle G,A\rangle$:

• Create a CFG $H$ by eliminating variable $A$ from the generation rules of $G$.

• Create a decider for $\text{A}_{\text{CFG}}$.

• For each string $w$ in $\Sigma^*$:

• Use the decider to check whether $\langle G,w\rangle\in\text{A}_{\text{CFG}}$ and whether $\langle H,w\rangle\in\text{A}_{\text{CFG}}$. If the former is yes and the latter is no, accepts.

It is easy to see that $D$ recognizes $\text{NECESSARY}_{\text{CFG}}$.
Note that there is no need to specify when or whether $D$ rejects.

You are on the right track on the undecidability.

Note that the right way is "to reduce $\text{ALL}_{\text{CFG}}$ to this" instead of "to reduce this to $\text{ALL}_{\text{CFG}}$".

The mental model is to view "$\text{ALL}_{\text{CFG}}$" as such a "huge and difficult" problem that it cannot be "reduced" to another small and easy problem. If we do find a reduction, the other problem must also be "huge and difficult", which is what we want.

StackExchange Computer Science Q#150380, answer score: 7