Automata B-Exam
January 1996
There are 4 questions worth 10 points each for a total of 40 points.
-
For any two integers p and q
denote
Apq = { x | x = p + nq, x >= 0, n -- integer }.
Show that the language
R = { ai | i element of Apq}
is regular.
-
Let
L = { an(a + b)n+mbm | n-odd, m-even}.
Is L a CFL? Justify your answer.
-
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.
-
Let L1 and L2 be languages.
- Suppose that there is a 2n time-bounded
reduction of L1 to L2, and
L2 is in DTIME(2n). What can
you conclude about L1?
-
Suppose that there is a log-space reduction of L1 to L2,
and L2 is the graph reachability problem.
What can you conclude about L1?