The first midterm exam will be in class Wednesday 25 March. Exams will be closed book and closed notes. This midterm will primarily cover chapter 2 and 3 of the text, though you should be familiar with the mathematical methods of chapter 0 and how recognizable, decidable, and context free languages relate to regular languages.

Midterm 2 Review

You should be able to define, explain, and apply the following concepts from Chapter 2:

  • Context free grammars

  • Context free languages

  • Pushdown automata (PDA)

  • Pumping lemma for context free languages

  • Closure properties of context free languages (union, concatenation, Kleene star)

Make sure you understand how your knowledge in this course fits together. I recommend that for context-free languages, you make sure you understand the following for each concept:

  • the definition

  • a technique to prove a language IS in this class

  • a technique to prove a language IS NOT in this class

  • some example languages in this class

  • some example languages not in this class

  • a list of operations that this class is closed under

We did not cover Ambiguity, Chomsky Normal Forms (end of 2.1), or Deterministic Context Free Languages in class (2.4), so you do not need to know those topics for the exam. You should know how to design a CFG or PDA for a language, but you do not need to know how to convert between them.

For Chapter 3, you should be able to define, explain, and apply the following concepts:

  • Turing machines

  • Turing machine variants (multitape, nondeterministic, enumerator)

  • Recognizable and decidable languages

  • The Church-Turing thesis

  • Example of recognizable and decidable languages.

Midterm 2 will not cover the undecidability.

You may use any of the proofs from class or text without needing to reprove them. You should be able to apply the techniques and concepts from those proofs to new problems. For the context free pumping lemma, I will provide the statement of the lemma on the exam, but you should be able to apply it to show a language is not context free.