Homework Due Tuesday, January 24
0.7, 0.9 (for this problem, use A={1,2,3} and B={4,5,6}), 0.10, 0.11, 0.12
Consider the relation S defined as follows. (1,1) is in S. If (a,b)
is in S, then so is (a+1,b+2a+1). S is the graph of a well-known
function. Determine what this function is, and then show (using induction)
that your solution is correct.
Do not bother to hand in 0.13 and 0.14, but do try to solve them before
you read the solutions. (Also, make sure that you understand the other
excercises in this chapter, even though you are not to hand them in.)
1.4.e, 1.6(c,g,i), 1.7.b, 1.9.a,
Homework Due Tuesday, January 31
1.10.c, 1.14.b, 1.15, 1.16, 1.17, 1.18(c,g,i), 1.21, 1.31, 1.34, 1.51
Homework Due Tuesday, February 7
1.29.b, 1.32 [Give a minimal DFA for the reversal of B], 1.35, 1.40.b, 1.46(a,c,d) [Note: some of these may actually be regular.], 1.49,
2.4.e, 2.6(b,d), 2.9, 2.14, 2.35
Homework Due Tuesday, February 14
2.5.e, 2.10, 2.11, 2.20, 2.23, 2.25, 2.28.a (why is your grammar unambiguous?),
Consider the following grammar:
S -> AB | CB | a | b
B -> AS | SC
A -> a
C -> c
Determine if the following strings are generated by the grammar: caaac, caaab
For Extra Credit: 2.24 (This is challenging.)
Homework Due Tuesday, February 21
2.30(a,d), 2.32
Give a DPDA for these languages: 2.6(a,b), 2.28(a)
For Extra Credit: 2.37.
Homework Due Thursday, March 1
3.6, 3.7, 3.8.b, 3.9.a,b, 3.12, 3.13, 3.14, 3.15, 3.18, 3.19 (hint: use the result of problem 3.18)
Homework Due Thursday, March 8
3.21, 4.10, 4.12, 4.17, 4.18, 4.24,
5.1, 5.2, 5.16, 5.24, 5.25
Homework Due Thursday, March 22
5.3, 5.14, 5.15, 5.21, 6.6, 6.13
(Extra Credit: I had originally assigned 5.33 too. The
"errata" page for this book mentions that this exercise
is more appropriate for Chapter 6. Indeed, the easiest way
that I see to solve this problem uses a "strong form" of the
recursion theorem. Try it for extra credit.)
Homework Due Thursday, March 29
6.22, 6.23, 6.24,
7.7, 7.12, 7.14, 7.17, 7.19, 7.20, 7.36 (This is easy; don't worry about
the fact that it is marked as challenging!)
(For extra credit: 6.25; HINT: if z is incompressible, then z must contain
a string of at least (log |z|)/2 one's.)
Homework Due Thursday, April 5
7.21, 7.41, 7.45, 8.1, 8.3, 8.8, 8.16, 8.20
For extra credit: 7.16, 7.44, 7.46
Homework Due Thursday, April 12
8.25, 8.26, 8.27, 9.7(e,f,g), 9.9, 9.12
Homework Due Thursday, April 19
9.13, 9.14, 9.16 (You can do the problem as given in the book for extra credit,
but for the assignment, merely show that TQBF is not in SPACE(log^4 n).), 9.19,
9.20
Take-Home Final
The final exam will be handed
out in class no later than Tuesday, April 24. The exam must be handed in by
4:00 PM on Monday, May 7.