Prelim 2 will be non-cumulative, although you are still expected to know the basic skills covered before prelim 1 (e.g. writing proofs and understanding definitions).
Here are some collected questions from past prelims and finals (solutions) There is always variation between semesters on the exact topics covered and the extent to which they are emphasized, so take the sample prelims with a grain of salt. I would expect most of these questions to take 10-15 minutes.
Update: Reasonable NFA-related questions might include determining whether a string is accepted by an NFA, giving an NFA to solve a (concrete) problem, or describing the language of an NFA.
The prelim will cover the material through early next week. Specifically:
functions, including functions whose domains and codomains are themselves sets of functions
definitions of injectivity, surjectivity, bijectivity
definitions of function composition, left- right- and two-sided- inverses, the relationships between those and 'jectivity
definitions of \(|A| \leq |B|\), \(|A| \geq |B|\), \(|A| = |B|\), and basic properties of these definitions.
definition of countable, diagonalization, various examples of countable and uncountable sets
finite cardinality; definition of \(|A| = n\).
counting: sum rule, product rule, quotient rule, \(n!\), \(n \choose k\), permutations, etc. Be able to apply these rules to solve combinatorics problems.
relations; binary relations, equivalence relations (reflexivity, symmetry, transitivity), equivalence classes, \(A / R\), well-defined functions from \(A / R\) to \(X\).
proofs by weak induction.
inductively defined sets, inductively defined functions, proofs by structural induction. Particularly the inductive definition of \(\Sigma^*\).
definition of a finite automata, be able to build finite automata for simple tasks and give specifications for each state, inductive proof of automata correctness. Building machines out of given machines (e.g. cross product construction for recognizing the union of recognizable sets). Definitions of the extended transition function and the language of a machine.
Material that will be covered between now and the exam:
Proving sets are not recognizable using the pumping lemma. Know examples of some non-recognizable sets.
Definition and operation of NFAs.