Study Guide for Test 1, COSC 157

The first test will be Friday, Sept. 28, in class.
The material is everything we've done in class, which
is basically Chapters 1 and 2 of the textbook.  In particular,
the following topics may appear:

 Deterministic Finite Automata
    Computing a trace on a given string (to decide if
    the string is accepted or not).
    Designing machines to recognize given strings.
 Nondeterministic Finite Automata
    Deciding when a string is accepted.
    Converting a Nondeterministic machine into
    a deterministic one.
 Regular Expressions
    Construction machines for union, complement,
    intersection, difference, concatenation of languages
    for given machines (Theorem 2.4.1).
    Building a machine to recognize the language
    of a given regular expression.
    Finding a regular expression which describes the language
    of a given machine.
 Nonregular Languages
    Using the Pumping Lemma (Lemma 2.5.1) to show that
    a language is not regular.
 State Minimization
    Compute the equivalence classes of indistinguishable
    states for a given machine.
    Construct a machine equivalent to a given one with a
    minimum number of states.