The final exam will be cumulative, but will concentrate more heavily on material covered since the second midterm. In addition to the material from the two midterms, we will be testing material through lecture 25 (Sipser section 5.1). The material presented in lectures 26 and 27 may be useful in firming up your understanding for the final, but the only thing we might test directly is knowing that CFG ambiguity is undecidable.

The overall look-and-feel of the exam will be similar to the final from last term (which is posted on the exams page). It will definitely include a reduction proof whose outline is similar to that of Rice's Theorem (or, equivalently, very similar to the proof of REGULAR_TM in Sipser). It will also include a question on the pumping lemma for regular languages.

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, 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 simulations in parallel (see homework 14, lecture 25).
  • 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 of Sipser.
  • Classify each of these standard problems as decidable, Turing recognizable, not recognizable but the complement is recognizable, or none of these.
  • For the decidable or recognizable problems, sketch an algorithm that decides or recognizes it. (Efficiency doesn't matter.)
• 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. Recognize when a decision problem does not fit the conditions of Rice's Theorem.
• Proving languages undecidable (very difficult parts)
  • We know this part of the material is hard. We'll ask questions on it, but we realize that even simple questions on reduction will seem very hard to many of you.
  • Understand the diagonalization proof that A_TM is undecidable. You don't have to be able to construct a whole proof like this from scratch.
  • Know how to figure out the language accepted by the auxiliary TM M_w used in the reductions that look like Rice's theorem. (E.g. like question 6 on quiz 6.)
  • Know how to prove that a language is undecidable using a reduction from another language already known to be undecidable. Proofs on the exam will have very simple/standard outline, similar to theorems 5.1-5.4 in Sipser.

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

• the pumping lemma for regular 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).