Say that a variable A in CFG G is necessary if it appears in every derivation of some string w ∈ G. Let NECESSARY CFG = {hG, Ai| A is a necessary variable in G}.
a. Show that NECESSARY CFG is Turing-recognizable.
b. Show that NECESSARY CFG is undecidable.