The second midterm will cover material from Lecture 9 through lecture 15 (13 March). The primary focus of the exam will be context-free languages. It will also cover the pumping lemma for regular languages and DFA minimization. There will be no questions on Turing machines.

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

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

• Underlying mathematics:
  • Correctly interpret a recursive definition and find an equivalent non-recursive definition.
  • Know that proving definition A equivalent to definition B requires proving BOTH directions. For example, proving that a grammar G generates language L requires proving that (a) every string generated by G is in L and also that (b) every string in L is generated by G.
  • Write an inductive proof where the induction is over
    • all parse trees produced by a grammar G (remove root and consider the subtrees under it)
    • all strings in a language L (remove first character, or divide string into smaller pieces)
    • all derivations allowed by a grammar G (remove first step and sometimes divide the rest into subsections)
    • all objects defined by a recursive definition (consider the sequence of rules applied to create each object)
• Regular languages
  • 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.
  • State the pumping lemma for regular languages.
  • Use the Pumping Lemma to prove that some language L is not regular.
  • Minimize a specific DFA and describe the general procedure for minimizing any DFA.
  • Describe a procedure for checking whether the language accepted by a DFA is non-empty.
• 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?
  • Define Chomsky normal form. Recognize whether a grammar is in this form. Produce a Chomsky normal form grammar that generates some specific language L. Describe the general procedure for converting a grammar to CNF.
• 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.
  • Construct a PDA to recognize some specific language L. Use special bottom-of-stack symbol, exploit non-determinism ("guessing") when required.
  • Describe the language recognized by some specific PDA.
  • Describe the procedure for making a simple 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. Sketch the algorithm for converting a PDA to a grammar or vice versa. Do the conversion (or parts of it) for concrete examples (e.g. convert a specific grammar into a PDA).
  • Be able to tell whether a specific language L is context-free. We will ask about languages that strongly resemble standard examples that are in the text (section 2.3) or lecture notes.
  • State the pumping lemma for context-free languages.
  • Use the Pumping Lemma to prove that some language L is not context-free.
  • 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.
  • Use closure properties to prove that a language is not context-free, given that we know some other specified language is not context-free.