## 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.