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:

Techniques

• Strong induction

• Inductively defined functions
  • examples: gcd, string reverse, delta-hat
• Equivalence classes
  • A/R, equivalence class, representative, well-defined functions on A/R

Number theory

• Euclidean division
• Euclidean gcd
  • Bezout's theorem
• base b representation
• equivalence mod m
• Z_m (integers modulo m)
  • how to add and multiply equivalence classes

Finite automata

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

• formal definitions
  • DFA as 5-tuple
  • extended transition function (delta hat)
  • language of a machine
• subset construction for converting NFA to DFA

• equivalence class construction for optimizing DFA

• NFAs with epsilon transitions and NFAs with regular expression transitions

Regular expressions

• regular expressions
  • kleene star, concatenation, union,
• language of a regular expression
• writing regular expressions for given language description

• converting regular expressions to NFAs and NFAs to regular expressions

• set of regular, DFA-recognizable, NFA-recognizable languages all the same