Math 342: Theory of Computation

General Information

Instructor: Chris Staecker (Personal Homepage)

Email: cstaecker@fairfield.edu

Office: BNW 16

Office Hours: T 10:30-11, 12-12:30, 1:30-2:30; W 10-11, 12-1, 2-3; F 10:30-11, 12-12:30 or by appointment

Textbook: Webber, Formal Language: A Practical Introduction

Class Meetings: TF 9:30-10:20, W 9:00-9:50 BNW 137

Final Exam: Tuesday May 8, 8:00AM

1/24: Homework #1 due: Chapter 1: 1, 2, 4 ("set former" is like what you see in #1a,b,d,e)
Chapter 2: 2, 3, 4acd, 7, 9ab
Selected solutions
1/31: Homework #2 due: Chapter 2: 5, 6
Chapter 3: 4d, 5 (Hint for part b: A - B = A ∩ B), 8, 9, 10
Selected solutions
2/7: Homework #3 due: Chapter 5: 1, 3acdf, 4ad, 5bd, 7a, 8b, 9, 10
Chapter 6: 3, 6 (start with the start state, and only draw states which can be reached. There should be only 6 reachable states.)
Selected solutions
2/14: Homework #4 due: Chapter 7: 1a-s, 2
Selected solutions
2/21: Homework #5 due: Chapter 10: 2, 4, 5, 6, 7, 10f, 11abe, 13bc
Selected solutions
2/23: Exam #1
3/7: Homework #6 due: Chapter 11: 4, 6, 8, 9
Chapter 12: 1bfhjk
Selected solutions
3/21: Homework #7 due: Chapter 12: 2befgj, 4abc (for c, there are two parse trees for "()()()"), 5b
Selected solutions
3/28: Homework #8 due: Chapter 13: 1, 2, 4, 5, 6aceg, 7
Selected solutions
4/4: Homework #9 due: Chapter 13: 12, 13
Chapter 14: 3, 4, 5, 6
Selected solutions
4/6: Exam #2
4/18: Homework #10 due: Chapter 16: 2 (use basically the same diagram), 3, 6, 12 (assume n>0)
Selected solutions
4/25: Homework #11 due: Chapter 17: 2, 3, 5, 6, 7
Selected solutions
5/2: Homework #12 due: HW 12 assignment
Course evaluation: Please do the survey!
5/8, 8:00AM: Final exam