Automata B-Exam January 1996

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} | i ∈ A_{pq}}

is regular.

2. Let

L = {a^{n}(a + b)^{n+m}b^{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_{1} and L_{2} be languages.

• Suppose that there is a 2^{n} time-bounded reduction of L_{1} to L_{2}, and L_{2} is in DTIME(2^{n}). What can you conclude about L_{1}?

• Suppose that there is a log-space reduction of L_{1} to L_{2}, and L_{2} is the graph reachability problem. What can you conclude about L_{1}?