Question

Say that a variable A in CFG G is necessary if it appears in every derivation of some string $\mathit{w}\mathbf{\in }\mathit{G}$. Let .

1. Show that NECESSARY_CFG is Turing-recognizable.
2. Show that NECESSARY_CFG is undecidable.

Short answer

1. NECESSARY_CFG is Turing-recognizable
2. NECESSARY_CFG is undecidable

Step-by-step solution

Turing-recognizable and Undecidability

Turing-recognizable

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e., TM halt and accept strings belong to language L and will reject or not halt on the input strings that doesn’t belong to language L.

Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Solution of part (a).

a).

Here we have to prove NECESSARY_CFG is Turing recognizable.

Let S be decider for Context Free Grammar A

Let us construct a Turing Machine M such that:

• Construct Context Free Grammar G/A by removing non-terminal A and all production that contain G
• Mention the string w one-by-one generated by G. Now we will run all such strings on S to check if w is generated by G/A.
• If string w is not generated byG/A , accept
  Else
  Keep searching and reject on other outputs.

Now, the language$L\left(\frac{G}{A}\right)$contain all or only those string w which belong to language G i.e., $w\in L\left(G\right)$.

So, our Turing Machine M will recognize such string w and accept it.

If A is not necessary for G, in such situation$L\left(G\right)=L\left(\frac{G}{A}\right)$and M will keep searching and rejecting unwanted string.

Thus, M recognize NECESSARY_CFG.