##
CPSC 433: Review for Exam 1

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 through Feb 16 (through Chomsky Normal Form)

- Readings:
Chs 1, 2, 3 (skim 3.4), 4 (skip 4.2.3, 4.2.4, and 4.4),
Ch 5 (skim 5.2.3 through 5.2.5, skim 5.3.3 and 5.3.4),
and Ch 7 (sec 1 only)

- Quizzes 1-5 and their solutions (given in class)

- Homework assignments 1-3 and their solutions
(given 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:

- How to define a set recursively, how to prove something
about the elements of the set inductively, and how the
recursion and the induction are related.

- Definition of regular languages.

- Definitions of the different kinds of finite
automata (deterministic, non-deterministic, with or without
epsilon transitions). Know the difference in the meaning
of language acceptance for deterministic and nondeterministic
machines.

- How to convert an epsilon-NFA to a DFA.

- The recursive definition of regular expressions.

- How to convert a regular expression to an epsilon-NFA.

- How to convert an epsilon-NFA to a regular expression.

- Be able to state and prove the pumping lemma for regular languages.

- Be able to use the pumping lemma to prove that certain languages
are not regular.

- Closure properties of regular languages and
how to use these facts to decide whether or not a language is
regular.

- Algorithms for deciding whether the language of a DFA is
empty, infinite, equal to the language of another DFA.

- Definitions of context-free grammar, parse tree, left-most
and right-most derivations.

- Constructing a CFG for a described language.

- Application of CFG to programming language syntax and compilers.
(Read about this in the textbook.)

- Ambiguous grammars vs. ambiguous languages.

- Definition of Chomsky Normal Form and how to convert a grammar to it.