Homework 10

CS 3810 – Summer 2008

  1. [4 points] Describe a Turing Machine that accepts { 0n | n is a power of 2 }. We want a high-level description of this machine in 10 or fewer clear English sentences. Do not give a list of transitions.

  2. [4 points] Describe a Turing Machine that, on input an, halts with am on the tape where m = n2. We want a high-level description of this machine in 10 or fewer clear English sentences. Do not give a list of transitions.

  3. [6 points] Show that the recursively enumerable languages are closed under

    1. union and

    2. intersection.

  4. [4 points] Show that { anbnanbnanbnanbn | n ≥ 1 } can be written as the intersection of two context free languages.