The first midterm will cover material through lecture 8 (7 February). Key skills that will be tested on the midterm include:

• Underlying mathematics:
  • Be familiar with standard notation for sets, quantifiers, alphabets, strings, and languages.
  • Know the definitions of basic set operations, especially cross-product and power set.
  • Know how to write an inductive proof.
  • Convert a recursive definition of a set to a non-recursive one.
  • Apply this knowledge of induction and recursive definition to sets of strings.
  • Be clear on how these definitions work for the special cases of the empty set and the empty string.
• DFA's
  • Given a set of strings, design a DFA to accept it.
  • Given a DFA, describe the set of strings it accepts.
  • Use the product construction to prove that regular languages are closed under intersection and union.
  • Show that regular languages are closed under set complement.
• NFA's
  • Given a set of strings, design an NFA to accept it, exploiting the extra features of NFA's (non-determinism, epsilon transitions).
  • Given an NFA, describe the set of strings it accepts.
  • Sketch the proof that regular languages are closed under union, concatenation, star, and string reversal. Expand a selected part of the proof into tuple notation.
  • Know the definition of a homomorphism, and that regular languages are closed under homomorphisms. (We haven't done much with them yet.)
  • Use the powerset construction to convert an NFA to a DFA. Convert simple concrete examples. Explain the general conversion algorithm.
• Formal definitions of automata
  • Specify an NFA or DFA using a state diagram.
  • Specify an NFA or DFA using tuple notation.
  • Calculate specific values for the transition function delta, for an NFA or a DFA.
  • Define the epsilon closure of a set of states. Calculate the epsilon closure for a specific input set.
  • Quote the formal definition of an NFA, of a DFA.
  • Define what it means for a DFA or NFA M to accept a string w. Define the language L(M) recognized by a DFA or NFA M.
• Modifying automata and adapting formal definitions
  • Describe precisely how to modify an arbitrary DFA or NFA to meet some goal, e.g. make it have only one accept state.
  • Describe a general procedure for building a DFA or NFA, when some design parameter (e.g. the alphabet size) may vary.
  • Prove some new closure property, where the proof is very similar to the proof of a familiar closure property.
  • Given the definition of a variant type of automaton such as a GNFA, do some of the above tasks with it. For example, modify the formal definition of acceptance for the new type of automaton.
• Regular Expressions
  • Be familiar with notation, including operator precedence (star groups more tightly than concatenation, which groups more tightly than union) and including common variations (e.g. + or ∪ for union)
  • Given a set definition, construct an equivalent regular expression. Given a regular expression, describe its language.
  • Convert a regular expression to an NFA. Explain the general conversion algorithm, or selected parts of it.
  • Convert a DFA to a regular expression: know that it's possible, convert small concrete examples, sketch the general algorithm.
  • Know informally what a GNFA is. (We won't ask you to quote back the formal definition.)