The second midterm will cover material through lecture 17 (24 October). However, we know that much of the Turing machine material is abstract and you've only done one homework problem on it. So we will only ask very elementary questions about Turing machines. The primary focus of the exam will be context-free languages. It will also cover the pumping lemma for regular languages.

You are expected to still remember basic facts about regular languages, but the exam won't probe for things that are easy to forget.

Here is a summary of the key skills that will be tested on the midterm:

• Underlying mathematics:
  • Know how to correctly interpret a recursive definition and find an equivalent non-recursive definition.
  • Be able to write inductive proofs involving sets of strings, recursive definitions, context-free grammar rules, and trees (e.g. parse trees).
• Regular languages
  • Use the Pumping Lemma to prove that some language L is not regular.
  • If you had trouble with the pumping lemma proofs on homeworks and aren't sure you are on top of this, go to HBS or office hours.
  • Be able to tell whether a specific language L is regular. Examples of non-regular langauges will be like (but perhaps not identical to) those in lecture notes, section 1.4 in the book, homeworks.
  • We won't ask questions about suffix languages
• Context-free grammars
  • Know the definition of a context-free grammar (tuple notation).
  • Design a context-free grammar that generates a specific language L.
  • Describe the language generated by a specific grammar G.
  • Draw a parse tree for a word w using a grammar G.
  • Know that a single string may have more than one (even a lot of) distinct parse trees. Produce examples illustrating this phenomenon. Interesting study question: can you write a grammar for which some string w has infinitely many distinct parse trees?
  • Be able to define Chomsky normal form, recognize whether a grammar is in this form, produce a Chomsky normal form grammar that generates some specific language L. (We won't be picky about the small differences from text to text in the exact definition of Chomsky normal form, e.g. what happens with the empty string.)
• Pushdown automata
  • Know how to specify a PDA using tuple notation and state diagrams, and convert between the two notations.
  • Know that PDA's are non-deterministic and that the deterministic variant recognizes a different (smaller) class of languages.
  • We won't ask you to formally define a deterministic PDA.
  • Construct a PDA to recognize some specific language L.
  • Describe the language recognized by some specific PDA.
  • Describe the procedure for making a very easy modification to an arbitrary PDA, e.g. give it a single accept state, make it empty the stack before accepting, allow it to push several characters at once (see p. 117).
• Context-free languages
  • Know that PDA's are equivalent to context-free grammars. Given a specific grammar, construct an equivalent PDA. (See picture at the top of p. 118.) We won't ask you to reproduce any other details of the equivalence proof.
  • Know that there is a pumping lemma for context-free languages. We won't ask you to state it or prove things using it.
  • Be able to tell whether a specific language L is context-free. We will ask about languages that strong resemble standard examples that are in the text (section 2.3) or lecture notes.
  • Know which basic operations (e.g. union, complementation) the context-free languages are closed under. For some specific operation (e.g. union) briefly explain why they are or aren't closed. See October 12th lecture.
• Turing machines
  • To get a good picture of what we might ask, imagine a simpler/smaller version of problem 1 on homework 6.
  • Know the tuple definition of Turing machine. Also what a configuration is.
  • Be able to define Turing recognizable and Turing decidable and explain the difference between the two definitions. (But no deep understanding of the consequences of that difference.)
  • Know that multi-tape and non-deterministic Turing machines are equivalent to ordinary ones. (But we won't expect you to reproduce the constructions.)
  • Draw a state diagram for a very simple behavior.
  • Turn a very simple state diagram into a high-level description of behavior.
  • Give a sample run (sequence of configurations) for a specific Turing machine on a specific input.