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

Question

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

1. Show that $\text{NECESSARY}_{\text{CFG}}$ is Turing-recognizable.
2. 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$:

1. Create a CFG $H$ by eliminating the $A$ variable from the derivations of $G$.
2. Create list of strings $w$ generated by grammar $G$.
3. Create a decider for $\text{A}_{\text{CFG}}$ and check if each string of $w$ can also be generated by $H$.
4. If $w$ strings cannot be generated by $H$ then accept.
5. 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.

Answer 1

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

1. Create a CFG $H$ by eliminating variable $A$ from the generation rules of $G$.
2. Create a decider for $\text{A}_{\text{CFG}}$.
3. For each string $w$ in $\Sigma^*$:
   1. 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.

Answer 2

Let $G$ be a context-free grammar over an alphabet $\Sigma$ with initial variable $S$. Create a new grammar $G'$ with a new initial variable $S'$, a new variable $A$, and transitions $S' \to S \mid A$, $A \to \sigma A$ for every $\sigma \in \Sigma$, and $A \to \epsilon$. You take it from here.