CPSC 433: Review for Exam 1
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)
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
- 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
- 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.