CPSC 433: Review for Exam 1
Spring 2006

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.