Midterm review

The midterm will take place in class on Thursday, October 10. There will be 5 true/false questions (no explanation necessary) in addition to several long-answer questions. You will have the full 80 minutes to write the exam, though it shouldn't take you that long.

The midterm will cover all the lectures up to Thursday, October 3, EXCEPT the one on well-founded induction and the one on learning algorithms.

1Things to know¶

• How to design automata (DFAs/NFAs). Show dead states only for DFAs.
• The pumping lemma
• How to determine & prove if a language is regular or not
  • If it's regular: draw the corresponding DFA or NFA diagram
  • If it's not: show that it's not pumpable (note that we won't be given any irregular, pumpable languages)
• Some algorithm about regular languages/expressions
  • Create a new algorithm for something
  • Can make use of algorithms that we've already studied (refer to them briefly; no need to go into detail)