(30 points) Say that a variable A in CFG G is necessary if it appears in...

 

Transcribed Image Text:

(30 points) Say that a variable A in CFG G is necessary if it appears in every derivation of some string wL(G). Let NECESSARY CFG = {(G, A) | A is a necessary variable in G}. (a) Show that NECESSARY CFG is Turing-recognizable. (b) Show that NECESSARY CFG is undecidable. (30 points) Say that a variable A in CFG G is necessary if it appears in every derivation of some string wL(G). Let NECESSARY CFG = {(G, A) | A is a necessary variable in G}. (a) Show that NECESSARY CFG is Turing-recognizable. (b) Show that NECESSARY CFG is undecidable.