CPSC 433: Review for Exam 2
Spring 2006

You may bring one 8.5 by 11 inch sheet of paper to the exam with your notes on it. You may write on both sides of it.

Review the following:

• Lectures on Feb 28 (PDA's) through Mar 28 (Church-Turing thesis).

• Readings:
  • Ch 6
  • Ch 7 sec 2, sec 3.3, sec 3.4, sec 4 (skim)
  • Ch 8 sec 1 (skim), sec 2, sec 3, sec 4, sec 5.1 (skim), sec 6

• Quizzes 6-9 and their solutions (given in class)

• Homework assignments 4 and 5 and their solutions (provided in class)

The format of the exam will be some short answers and some "work-out" problems. Difficulty will be in between the quizzes and the homework. Here are some suggestions for things to know:

• Definition of a push-down automaton.

• Constructing a PDA for a described language.

• PDAs and CFGs are equivalent models of computation.

• How to transform a context-free grammar into an equivalent PDA (but not the other direction).

• rough idea of proof of pumping lemma for CFLs (i.e., the picture of the tree)

• how to apply the pumping lemma for CFLs to prove that certain languages are not context-free

• CFLs are closed under union, concatentation, and star (and why); they are not necessarily closed under intersection or complement

• intersection of a regular language and a context-free language is context-free but not necessarily regular

• definition of a (deterministic) Turing machine, how it computes, how it accepts; variations (e.g. multitape) that don't change computational power

• definitions of recursively enumerable and recursive languages

• definition of a nondeterministic Turing machine, how it computes, how it accepts

• equivalence of acceptance by halting and acceptance by final state for TMs

• equivalence of deterministic and nondeterministic TMs

• r.e. languages are a strict superset of recursive languages; recursive languages are a strict superset of context-free languages