CS 3133
C term 2017
Worcester Polytechnic Institute

Here is a link to the lecture notes for the course.

This will be updated during the term.

This is the primary resource for course content, and most importantly, contains the exercises that comprise your homework assignments. Read more below…

Course Information


  • Dan Dougherty: dd at cs dot wpi dot edu
  • Office hours (Fuller Labs 231):
    • Mondays and Thursdays 4–5 (i.e., after class)
    • Tuesday and Fridays 2–3 (i.e., before class)

TA+SA office hours (in Fuller Labs A22)

  • John Lee jtlee at wpi dot edu
  • Shijian Li sli8 at wpi dot edu
  • Hang Cai hcai at wpi dot edu

    office hours TBD

Course mailing list: cs3133-all at cs dot wpi dot edu

Sending to this mailing list will reach all the registered students in the course, as well as the instructor.


There is no required textbook for the class. I will post notes online.


Your course grade will be based on four exams, as described below.


Exams will be given on the following evenings, in our classroom.

  • Exam 1 (worth 10%) : Thu Jan 19, 7 – 9 pm
  • Exam 2 (worth 30%) : Thu Feb 2, 7 – 9 pm
  • Exam 3 (worth 30%) : Thu Feb 16, 7 – 9 pm
  • Exam 4 (worth 30%) : Fri Mar 3, 4–6 pm

    Note that Exam 4 is immediately after the last class period.

This is important: If there is any reason why taking an exam on any of those evenings would create a difficulty for you, you must come explain why by Tuesday Jan 17. If you don't talk me before then, then I will consider that you have no prior commitment for those dates.


Your homework is precisely this: to do the exercises in the lecture notes sections we are covering. This is the most important part of the course: you can only learn stuff by doing stuff. The exams will be based quite closely on these exercises.

Since the class is so large, I cannot grade your homework, so I will not collect it. Solutions to most of the exercises will be made available, but only the day before the exams. The idea is that you should grapple with the problems without the solutions available, that's the best way to learn. But I'll give solutions before the exam so you can check your work or see how to do problems that you got truly stuck on.

Other Resources

The course content is well-established: the core topics comprise a set of techniques that everyone agrees should be mastered by every computer scientist. As a consequence, there are any number of good textbooks for this material. But the good texts are all way too expensive. That's a big reason why I am providing notes online. But here are some good texts that you might find useful as a supplement.

Available via the library

The following text is a favorite of mine

  • Automata and Computability
    Dexter Kozen

It is available as an electronic resource via the WPI library. I suggest that you bookmark it for yourself and use it as a resource to supplement the notes I provide.

Other good resources

  • Automata Theory, Languages, and Computation
    John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
  • Introduction to the Theory of Computation
    Michael Sipser
  • Languages and Machines: An Introduction to the Theory of Computer Science
    Thomas Sudkamp


2017 Jan 11 09:03:30 : still working on the details here

class date topic reading
01 R Jan 12 functions  
02 F Jan 13 cardinality  
  M Jan 16 (MLK Day, no class)  
03 T Jan 17 strings and languages  
04 R Jan 19 strings and languages  
    EXAM 1  
05 F Jan 20    
06 M Jan 23    
07 T Jan 24    
08 R Jan 26    
09 F Jan 27    
10 M Jan 30    
11 T Jan 31    
12 R Feb 2    
    EXAM 2  
13 F Feb 3    
14 M Feb 6    
15 T Feb 7    
16 R Feb 9    
17 F Feb 10    
18 M Feb 13    
19 T Feb 14    
  R Feb 16 (Advising Day, no class)  
    EXAM 3  
20 F Feb 17    
21 M Feb 20    
22 T Feb 21    
23 R Feb 23    
24 F Feb 24    
25 M Feb 27    
26 T Feb 28    
27 R Mar 2    
28 F Mar 3 review  
    EXAM 4  

Academic Honesty.

The details of the university's policies and procedures can be found here.

My response to any sort of cheating on will be to pursue the strongest remedies available to me.

Date: 2013-12-15 16:33:39 EST

HTML generated by org-mode 6.33x in emacs 23

Author: dd

Author: Dan Dougherty

Created: 2017-01-11 Wed 09:03

Emacs 25.1.1 (Org mode 8.2.10)