Prelim 2 study guide
=================
Prelim 2 will primarily cover material covered in lecture and homework since
prelim 1. Here are some [sample questions](p2-sample.pdf). Here are
[solutions](p2-sample-sol.pdf). See also the review questions listed in the
lecture notes.
As always, previous semesters covered material to different depths. I have
filtered the sample questions based on the topics we've covered, but some topics
we've covered more or less, so the difficulty may be different.
Here is a (potentially incomplete) set of topics:
### Probability
- There were a few topics that you hadn't had much coverage on for prelim 1:
indicator variables, weak law of large numbers. You also have had more
practice using and reasoning about random variables on HW 6. A probability
question is possible but not promised.
- You are not directly responsible for hashing or the probabilistic counting
algorithm covered in lecture. Any questions related to this will give you
any relevant definitions or properties.
### Induction
- Be able to give and interpret inductively defined sets and functions
- Be able to write proofs by structural induction
- Know the inductive definitions of strings
- Be comfortable with inductive proofs/definitions using pairs; understand what
inductive hypotheses/recursive function uses are valid, and why
### DFA
- Be comfortable converting between pictures and formal notation
- Be able to build DFA for simple concrete problems
- Understand the abstract DFA constructions we've done for union of languages,
DFA optimization, and conversion from NFA. Be able to apply them to concrete
problems
- Be able to prove a DFA is correct
- Know and be able to apply the pumping lemma. Understand the proof of the
pumping lemma
### NFA
- Know definitions (NFA, extended transition function, language of NFA, etc.)
- Be able to draw an NFA, decide whether a string is accepted by a given NFA,
describe the language of a given NFA
### Regular expressions
- Know definitions (Regular expression, language of a RE, whether a string is matched)
- Be able to write a regular expression, decide whether a given string is matched
by a regular expression, etc.
### Kleene's theorem
- Know Kleene's theorem. Understand the proofs of various parts of Kleene's
theorem. Be able to apply the various translations (NFA → RE, RE → NFA, NFA → DFA, DFA → NFA)
- Be able to apply Kleene's theorem to translate questions about regular
languages to questions about recognizable languages, and vice-versa