There are 4 questions worth 10 points each for a total of 40 points.

1. For any two integers p and q

   denote

   A_pq = { x | x = p + nq, x >= 0, n -- integer }.

   Show that the language

   R = { aⁱ | i element of A_pq}

   is regular.

2. Let
   L = { aⁿ(a + b)^n+mb^m | n-odd, m-even}.

   Is L a CFL? Justify your answer.

3. Let the language L be recursively enumerable but not recursive. Show that for any Turing machine M that accepts L there are infinitely many strings on which M does not halt.

4. Let L₁ and L₂ be languages.
   • Suppose that there is a 2ⁿ time-bounded reduction of L₁ to L₂, and L₂ is in DTIME(2ⁿ). What can you conclude about L₁?
   • Suppose that there is a log-space reduction of L₁ to L₂, and L₂ is the graph reachability problem. What can you conclude about L₁?