Due: Tuesday, January 27.
Sipser, page 169, problem 4.5.
Sipser, page 169, problem 4.10. (Hint. Just describe an algorithm that determines whether a given DFA accepts a string containing an odd number of 1's. How can you mark the states that are reachable by strings that contain an odd number of 1's? How about an even number of 1's?)
Sipser, page 170, problem 4.17. (Hint. What if y is a positive integer indicating a time limit (number of steps) that a program can run? Every computation that terminates must terminate in some number of steps. Also, given any program, it is possible to run it with a time limit, either getting a result or the answer "the program failed to terminate within the time limit.")
Sipser, page 170, problem 4.18. (Hint. You will need to use the assumption that A and B are co-partially computable. That means the there is a program that terminates just when its input is not in A, and another program that terminates just when its input is not in B. Use those programs to build a program for set C. There is no need to write a definition of C; whatever your program says is, by definition, correct. Remember that your program for C must halt on every input, and answer either 0 or 1. Be sure to show that A is a subset of C and B is a subset of the complement of C.) (Hint 2. You must use the fact that A and B are disjoint. So no x can be in both A and B.)