Math 342: Theory of Computation

General Information

Instructor: Chris Staecker (Personal Homepage)

Email: cstaecker@fairfield.edu

Office: BNW 16

Office Hours: W 10-1, R 10-12 or by appointment

Textbook: Webber, Formal Language: A Practical Introduction

Class Meetings: TF 12:30-1:20, W 1:00-1:50 NHS 405

Final Exam: Friday May 3, 11:30AM

1/30: 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
2/6: 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/13: Homework #3 due: Chapter 5: 1, 3acdf, 4ad, 5bd, 7a, 8b, 9b, 10
Chapter 6: 3, 6
Selected solutions
2/20: Homework #4 due: Chapter 7: 1a-s
Selected solutions
2/22: Exam #1
3/6: Homework #5 due: Chapter 7: Give a regular expression and an NFA for #1g, Convert the NFAs in #4, 5, 6 to regular expression
Chapter 10: 4ad, 5cd, 6, 7b, 10f, 11abe, 13bc
Selected solutions
3/13: Homework #6 due: Chapter 11: 2, 4, 6, 8, 9 (for all these, use derivatives, not the pumping lemma)
Chapter 12: 1bcfhjkqr
Selected solutions
3/27: Homework #7 due: Chapter 12: 2efg, 4abc (for c, there are two parse trees for "()()()"), 5b
Chapter 13: 2, 4
Selected solutions
3/29: Exam #2
4/10: Homework #8 due: Chapter 13: 2, 4, 5, 6aceg, 7, 12, 13
Chapter 14: 3, 4, 5, 6
Selected solutions
4/17: Homework #9 due: Chapter 16: 1, 2 (use basically the same diagram), 3, 6
Selected solutions
4/30 (or whenever): Homework #10 due: Chapter 16:12 (assume n>0), 13
Chapter 17: 2, 3, 5, 7
5/3, 11:30AM: Final exam