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