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

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.

#### 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.

• Perfect, thank you so much! Apr 5 at 13:32

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.

• Amazing, thank you!! Apr 5 at 13:31