CSE 417 Problem Set 2, Due January 27

1. In this problem all languages are over the same alphabet Sigma. The complement of a language L is the set of all strings over the alphabet which are not in L. All but one of the following statements are true.Identify the false statement and prove the others by giving high level dedscriptions of Turning Machines.

  • The complement of any Turing-decidable language is Turing-decidable.
  • The complement of any Turing-recognizable language is Turing-recognizable.
  • The union and intersection of two Turing-decidable languages are Turing-decidable.
  • The union and intersection of two Turing-recognizable languages are Turing-recognizable.

    2. A graph is called bipartite if there is an assignment of a color to each vertex such that each vertex is assigned either the color "red" or "blue" and no two vertices of the same color have an edge between them.

  • Give an example of a graph that is not bipartite.
  • By giving a high-level description of a Turing machine, prove that the set of encodings of bipartite graphs is Turing-decidable ( i.e., it is decidable whenther a given graph is bipartite)

    3. Sipser, problem 3.16

    4. Sipser, problem 4.7

    5. Sipser, problem 4.8

    6. By giving a high-level description of a Turing machine, prove that th following problem is Turing-decidable: toe determine, given the encoding of a Turinng machine M and input string w, whether M ever moves its head to the left when started on input w.