CS 3133
C term 2017
Worcester Polytechnic Institute

This page is no longer being maintained, activity has been moved to the Canvas page for the course.

What's New

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)

Please note the one-time-only change to TA hours on Wednesday Jan 19

  • John Lee jtlee at wpi dot edu
    • Thursdays 9 – 12 am
  • Shijian Li sli8 at wpi dot edu
    • Wednesdays 6–9 pm
  • Hang Cai hcai at wpi dot edu
    • Wednesdays 2–5 pm

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


class date topic lecture notes reading
01 R Jan 12 functions Ch 1
02 F Jan 13 cardinality Ch 2
  M Jan 16 (MLK Day, no class)  
03 T Jan 17 strings and languages Ch 3
04 R Jan 19 exam 1 review  
    EXAM 1  
05 F Jan 20 finite automata introduction Ch 4
06 M Jan 23 more examples; product construction Ch 4
07 T Jan 24 eliminating non-determinism Ch 5
08 R Jan 26 nil-transitions; encoding Ch 6,7
09 F Jan 27 the distinguishability relation Ch 3
10 M Jan 30 regular expressions; from regular expressions to automata Ch 9,10
11 T Jan 31 proving languages non-regular Ch 8
12 R Feb 2 exam 2 review  
    EXAM 2  
13 F Feb 3 from NFA to regular expressions  
14 M Feb 6 grammars  
15 T Feb 7 context-free grammars introduction  
16 R Feb 9 parse trees and ambiguity  
17 F Feb 10 refactoring context-free grammars  
18 M Feb 13 parsing 1  
19 T Feb 14 parsing 2  
  R Feb 16 (Advising Day, no class)  
    EXAM 3  
20 F Feb 17 Turing machines  
21 M Feb 20 (semi-)decision procedures  
22 T Feb 21 decision problems for FAs and CFGs  
23 R Feb 23 the halting problem  
24 F Feb 24 reducibility  
25 M Feb 27 more undecidable problems  
26 T Feb 28 more undecidable problems  
27 R Mar 2 Rice's theorem  
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.

Author: Dan Dougherty

Created: 2017-01-27 Fri 10:15

Emacs 25.1.1 (Org mode 8.2.10)