Automata B-Exam May 1996

There are 3 questions worth 10 points each for a total of 30 points.

1. Let L_{n} = {x ∈ {0, 1}^{∗} | x is a binary number that is multiple of n}. Prove that for each n ≥ 1 the language L_{n} is regular.

Hint: Prove that there are at most n equivalence classes and apply Myhill–Nerode’s Theorem.

2. Let L be a language. Prove that L is recursively enumerable if a recursive language D exists such that L = {x | ∃y such that xy ∈ D}.

3. A spanning tree of a graph H is any subgraph of H which is a tree and contains all vertices of H. The spanning tree problem is to decide, given a graph G and a tree T, whether T is isomorphic to any spanning tree of G. Prove that the Hamiltonian cycle problem is log-space reducible to the spanning tree problem.