The final exam will be cumulative, but will concentrate more heavily on material covered since the second midterm. In addition to the material on previous exams, we will be testing material through Section 5.2 in the book. Or, equivalently, material through the April 19th lecture, plus the material on Post's correspondence problem in the April 24th lecture. Material presented after that point may be useful in firming up your understanding for the final, but won't be tested directly.

Here are some specific topics from earlier in the course which are particularly worth reviewing:

• the pumping lemma for regular languages, and the similar one for context-free languages
• strong induction (e.g. on parse trees or derivations)
• the product construction for recognizing the union or intersection of two regular languages
• the subset construction for converting an NFA to a DFA
• designing a PDA which exploits non-determinism
• closure properties for regular and context-free languages
• use tuple notation to describe how to modify an input machine (e.g. a PDA) to produce a new machine (e.g. a similar PDA which empties its stack before accepting).

The new material for this exam includes:

• Turing machines
  • Formalism: tuple notation, configurations, accepting sequences of configurations.
  • Definition of Turing-recognizable and Turing-decidable, and especially how they differ.
  • Given a Turing machine's state diagram, describe the machine's behavior and language. Produce a sequence of configurations for a specific input string.
  • Design a Turing machine that accepts a specific language, enumerates a specific language, and/or behaves in a specific way. Describe it using a state diagram (very simple problems only!) or pseudo-code.
• Simulations
  • Simulating a new type of Turing machine with a normal one, e.g. multiple tapes, doubly-infinite tape, preloaded constant string.
  • Dovetailing/interleaving: simulating a non-deterministic TM with a deterministic one (Theorem 3.16), running several TM's in parallel on a single TM (see homework 11).
  • Enumerators: we saw Theorem 3.21 relating Turing-recognizability and enumeration. Know the relationship and also how the proof works.
  • We're not going to make you produce a long, complex construction in full detail. Rather, concentrate on understanding the key ideas in the above constructions and theorem proofs.
• Encodings
  • Encode a graph or other complex data structure as a string or ASCII file.
  • Encode a machine (DFA, PDA, Turing machine, etc) as a string or ASCII file.
  • Specific details of the particular encoding don't matter. Understand the general concept of how encodings are designed.
  • Define a computation history and explain what's involved in checking that it's valid.
• Decidable and undecidable problems
  • Know what a linear bounded automaton is.
  • Know the definitions of standard decision problems involving regular languages, context-free languages, Turing machines, linear-bounded automata. E.g. E_DFA, A_TM. See sections 4.1 and 5.1.
  • Classify each of these standard problems as decidable, Turing recognizable, co-Turing recognizable, or none of these.
  • For the decidable or recognizable problems, sketch an algorithm that decides or recognizes it. (Efficiency doesn't matter.)
  • Know what Post's correspondence problem is, and know the basic outline of how we proved that it's undecidable.
• Proving languages undecidable (somewhat difficult parts)
  • Know that a language is decidable if and only if the language and its complement are both recognizable.
  • Know that decidable languages are closed under complement, but recognizable languages aren't.
  • Prove that a language is undecidable or not recognizable, using a simple proof by contradiction that relies on closure properties or similar basic facts.
  • Know the statement of Rice's theorem. Recognize when a decision problem is covered by this theorem and, thus, is undecidable.
  • Identify whether some Turing machine behavior property is decidable and explain why or why not. (Simple examples only.)
• Proving languages undecidable (very difficult parts)
  • We know this part of the material is hard. We'll ask questions on it, but they will be relatively simple questions and not all of you will answer them successfully.
  • Write a simple diagonalization proof, e.g. show that the reals are uncountable, show that there are more languages than Turing machines (Theorem 4.18).
  • Understand the diagonalization proof that A_TM is undecidable, even if you aren't sure you fully believe in it.
  • Know how to prove that a language is undecidable using a reduction from another language already known to be undecidable.