1. The numbers refer to the textbook.

2. Write clearly and legibly. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length.

3. Don't forget to acknowledge all sources of assistance. Unless otherwise instructed, you must write up your homework on your own. Turn in your homework together with this cover sheet.

4. Homework is always due at the beginning of class.

• Exercise 9.1.3 (b). Read the solution to part (a) for help.

• Exercise 9.2.1

• Read the the statement of Exercise 9.2.3, especially the Hint. (There is nothing to turn in.)

• Exercise 9.2.6 (a), (b) and (c), for both the r.e. languages and for the recursive languages. (So there are 6 parts to this problem.) Even though the solution for (a) is on the text web site, you must write your solution in your own words.

• Exercise 9.3.4 (a) and (b) Hint: Read the solution to part (d) to get an idea how to show a language is not r.e. They show that L_e is reducible to the given problem, i.e., the given problem is at least as hard as L_e. Since L_e is not not r.e. (cf. Theorem 9.10), the given problem is not r.e.

• Read the solution to Exercise 9.3.6. The point is that certain things about Turing machines *are* decidable (e.g., how they behave up to a certain point), even though properties of their languages are not. (There is nothing to turn in.)

• Exercise 9.3.7 (a). Even though the solution is on the text web page, you must write the solution in your own words.

• Exercise 10.1.6 (b) and (c). Even though the solution is on the text web page, you must write the solution in your own words.

• Exercise 10.1.7 (b) and (c).

• Exercise 10.3.2

• Exercise 10.4.1. Even though the solution is on the text web page, you must write the solution in your own words.

• Exercise 10.4.4 (a).

• Exercise 7.3.2.

• Exercise 7.4.1 (b)

• Exercise 8.2.2 (c). Draw the TM's transition function as a state transition diagram. Include an intuitive description of how it works.

• Exercise 8.2.4 (a) and (b). It is particularly important to write your solution in your own words!

• Consider the NTM in Exercise 8.4.2. Give all computations of the TM on input 011, organized as a tree.

• Read the solution to Exercise 8.4.5. (There is nothing for you to turn in for this.)

• *** this is the complete assignment ***

• PROGRAMMING ASSIGNMENT 2 to simulate a nondeterministic Turing machine. Details are here. Unlike the rest of HW 5, which is due April 4, it will be due April 13.

For all problems that ask you to design a PDA, you must include a prose description of the intuition of what your PDA is doing, i.e., what the different states represent. This will make it possible for you to get extra credit.

• Refer to Exercise 6.1.1: Draw the generalized state transition diagram for the PDA. Then show all the reachable ID's (in a tree format similar to Fig. 6.3) when the input is 010.

• Exercise 6.2.1 (c).

• Exercise 6.2.2 (b).

• Exercise 6.2.6 (a).

• Exercise 6.3.2.

• Exercise 6.3.5 (b).

• Exercise 6.4.2 (b).

• Exercise 7.2.1 (b) and (c) and (e).

• Give a context-free grammar for the language {a^i b^j c^k : i > j + k}.

• Give a context-free grammar for the language {a^i b^j c^k : i < j or i > k}.

• Exercise 5.1.2 (c)

• EXTRA CREDIT: Exercise 5.1.3

• Exercise 5.2.1 (c)

• Exercise 5.3.2 (the solutions are on line so be sure to write your answer in your own words)

• Exercise 5.4.5 (b)

• Exercise 7.1.5

• Exercise 7.1.6

• Exercise 3.1.1 (b) and (c)

• Exercise 3.1.2 (b)

• Exercise 3.2.3

• Exercise 3.2.4 (c)

• Exercise 4.1.1 (d), (e), and (f) (p. 129)

• Exercise 4.1.2 (d), (g), and (h)

• Exercise 4.1.4 (d)

• Exercise 4.2.6 (c)

• Exercise 4.2.13 (b)

• Exercise 4.3.2

• PROGRAMMING ASSIGNMENT to simulate a DFA. Details are available here.

• The Fibonacci numbers, F(0), F(1), F(2), ... are defined recursively like this:
  Base cases: F(0) = 0, F(1) = 1.
  Recursive: For n > 1, F(n) = F(n-1) + F(n-2).
  Prove using induction on n that for all n >= 0 and m >= 1, F(n+m) = F(m)*F(n+1) + F(m-1)*F(n).

• Consider the set U of expressions defined recursively like this:
  Base cases: The digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 are in U.
  Recursive: Two combining operations are defined:
  • If E1 and E2 are expressions (in U), then so is "E1 + E2".
  • If E is an expression (in U), then so is "(E)".
  Prove using induction on the number of combining operations used to create the expression that every expression in U has an equal number of left and right parentheses.

• Exercise 2.2.4, (b) and (c)

• Exercise 2.2.5, (a) through (d)

• Convert to a DFA the NFA of Figure 2.15 with n = 3. Use the algorithm presented in class.

• Exercise 2.3.4, (b) and (c)

• Exercise 2.5.3, (a) and (b)