##
CPSC 433: Review for Exam 2

Spring 2006

*The exam will be cumulative in the sense that you are still
responsible for knowing the material we covered on the first exam.
However, the focus of the exam is on material covered ***since**
the first exam.
**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