CSE 105: Theory of Computation (Spring, 2006)

Home | Syllabus | Schedule | Exams | Homework | Sections

Homework

Homework is essential to understanding and learning the material. Exams will be similar to the homework problems. Homework will be assigned, but will not be collected or graded. If you'd like your homework to be graded, turn it in to the TA or the Instructor.

The quizzes will be at the beginning of class and will consist of several of the homework problems assigned for that day. For example, the quiz on April 11 will be comprised of several of the homework problems assigned for April 11.

These assignments are a minimum; you'll be well-rewarded by doing additional problems. You need to have lots of practice in solving problems. Consider doing every exercise and every third problem.

There are a few corrections to the book. I suggest you make corrections to the book at the beginning of the quarter; it's frustrating trying to figure out why you got a problem wrong only to realize the solution is incorrect.

Day homework is due Homework Homework solutions
April 11 Chapter 0: 0.1-0.12
Chapter 1: 1.1, 1.2, 1.3, 1.4g, 1.5g, 1.7d, 1.7g, 1.8b, 1.9a, 1.33, 1.36, 		text , diagrams
April 18 Chapter 1: 1.16, 1.18, 1.19, 1.20 (c-f), 1.21, 1.29, 1.46, 1.49, 1.55 (a-e) solutions
April 25 Construct a DFA with minimal number of states that recognizes the same language as the following FSA:
Chapter 2: 2.1, 2.3, 2.4		 solutions
May 1 Chapter 2: 2.5, 2.6, 2.7, 2.14, 2.27 solutions
May 9 Chapter 2: 2.11: Convert the CFG G4 given in Exercise 2.1 ...
2.30: Use the pumping lemma ...
2.31: Let B be the language of all palindromes...
2.39: Refer to problem 1.42 for the definition of the shuffle operation...
 solutions
May 16 Chapter 3: 3.2: This exercise concerns TM M1...
3.5: Examine the formal definition of a Turing machine ...
3.14: A queue automaton is like a ...
 solutions
May 23 Chapter 3: 3.7, 3.8, 3.22
Chapter 4: 4.6, 4.7
 solutions
May 30 Chapter 5: 5.3, 5.9, 5.12, 5.15, 5.17, 5.30(c)
Show that the language REINCF = {(G, RE)| G is a CFG and RE is a regular expression, and L(RE) is contained in L(G)} is undecidable.
 solutions
June 6 Formulate all these problems as languages and show that they are undecidable by reducing a known undecidable language. Do not use Rice's theorem.
  • Consider the problem of whether a Turing machine with a stay option (where the tape head stays stationary rather than moving left or right) every actually stays on any input.
  • Consider the problem of whether a Turing machine ever enters its reject state on any input.
  • Consider the problem of whether a Turing machine ever enters its accept state on any input.
  • Consider the problem of whether a two-way Turing machine ever moves to the left of starting tape head position on any input.
  • Consider the problem of whether three Turing machines recognize the same language.
  • Consider the problem of whether two Turing machines recognize disjoint languages. That is, are L(M1) and L(M2) disjoint sets?
Show that the following problem is decidable:
  • Consider the problem of whether a Turing machine on input w ever reads a blank.
  • Consider the problem of whether a Turing machine on input w and input k accepts w within k steps.
solutions
June 13 Chapter 7: 7.1 (a-d), 7.5, 7.6, 7.9, 7.11
 solutions