Prelim 2 topics

Everything covered in lecture through Monday 10/26 is in scope; Material covered by the homework will likely receive more emphasis in the exam, as will material that was not in scope on the first prelim.

Here are the second prelims from the last two semesters: fall 2014 and spring 2015. The depth of coverage of topics was substantially different during those semesters, so don't use these exams to calibrate your expectations! For example, we have not yet covered proving that a language is NOT regular, which was in scope for both of those exams. We also have not covered structural induction.

Here is a (potentially non-exhaustive) list of topics covered since prelim 1:


Number theory

Finite automata

DFAs, NFAs - informal definitions, drawing machines - executing machine on a given input - constructing a machine to recognize a language

Regular expressions