Prelim 2 study guide

Prelim 2 will primarily cover material covered in lecture and homework since prelim 1. Here are some sample questions. Here are solutions. 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