2. Reducibility (16 points)

1. (1) (10 points) For each of the following languages either prove it is undecid- able using a reducibility proof or show it is decidable by giving pseudocode for a TM that decides it:

   1. (a) Let FINITETM = {M | M is a TM and M accepts a finite number

      of strings}

   2. (b) Let ALLTM = {M | M is a TM and M accepts every string}

   3. (c) Let HALTLBA = {B,w | B is an LBA and B halts on input w}

   4. (d) Let MORECFG = {G1,G2 | G1 and G2 are CFGs where |G1| < |G2|

      (i.e., G2 accepts strictly more strings than G1}

   5. (e) Let EMPTYCFG = {G | G is a CFG and G generates }

2. (2) (2 points) Show that EQCF G = {G1, G2 | G1 and G2 are CFGs where L(G1) = L(G2} is co-Turing-recognizable.

3. (3) (4 points) A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of testing whether a given state in a Turing machine is a useless state. Formulate this problem as a language and show that it is undecidable.

   Hint: Consider the language ETM and whether the accept state is a useless state.