Homework Due Wednesday, January 25

0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 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). Show (using induction) that S is a familiar function.
Do not bother to hand in 0.13 and 0.14, but do try to solve them before you read the solutions.

Homework Due Wednesday, February 1

1.4.e, 1.6(c,g,i), 1.7.b, 1.9.a, 1.10.c, 1.14.b, 1.15, 1.16, 1.17, 1.18(c,g,i), 1.31, 1.34, 1.51, 1.64

Homework Due Wednesday, February 8

1.21, 1.29, 1.32, 1.33, 1.35, 1.36, 1.37, 1.40.b, 1.46(a,c,d), 1.49 (is there an error in the book?)

Homework Due Wednesday, February 15

2.4.e, 2.5.e, 2.6(b,d), 2.9, 2.10, 2.13, 2.14, 2.16, 2.35
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

Homework Due Wednesday, February 22

2.11, 2.20, 2.22, 2.23, 2.25, 2.28.a (why is your grammar unambiguous?), 2.30(a,d), 2.32
For Extra Credit: 2.24, 2.37 (these are challenging)

No Homework Due Wednesday, March 1

There is a midterm on that day.

Homework Due Wednesday, March 8

3.6, 3.7, 3.8.b, 3.9.a,b, 3.12, 3.13, 3.14, 3.15

Homework Due Wednesday, March 22

3.18, 3.19 (hint: use the result of problem 3.18), 3.21, 4.10, 4.12, 4.17, 4.18, 4.24

Homework Due Wednesday, March 29

5.1, 5.2, 5.3, 5.14, 5.15, 5.16, 5.21, 5.24, 5.25, 5.30

Homework Due Wednesday, April 5

6.1, 6.6, 6.13, 6.22, 6.23, 6.24, (for extra credit: 6.25)

Homework Due Wednesday, April 12

7.7, 7.12, 7.14, 7.17, 7.19, 7.20, 7.21, 7.36 (this is easy; don't worry about the fact that it is marked as challenging!), 7.41
For extra credit: 7.16, 7.44, 7.46

Homework Due Wednesday, April 19

8.1, 8.3, 8.8, 8.16, 8.20, 8.25, 8.26, 8.27

Homework Due Wednesday, April 26

9.7(e,f,g), 9.9, 9.12, 9.13, 9.14, 9.16, 9.20

Take-Home Final

The final exam will be handed out in class on Wednesday, April 26. The exam must be handed in by noon on Friday, May 5.