CS 373: Introduction to Theory of Computation

Spring 2013

The first midterm will cover material through lecture 10 (on pumping lemma). This corresponds to material in Chapters 0 and 1 of the Sipser book (edition 2 and 3). Key skills that will be tested on the midterm include:

• Underlying mathematics:
  • Familiarity 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 describe sets precisely using set notation and set operations.
  • Know how to critically evaluate and write proofs, like proofs by contradiction, etc.
  • Know how to critically evaluate and write inductive proofs.
  • Learn to understand inductive definitions.
  • Understand how inductive proofs and definitions go hand-in-hand.
  • Know how to write inductive definitions.
• Formal Definitions:
  • Know the formal definitions of: automata (DFA, NFA); acceptance of string (for DFA and NFA); language recognized (for DFA and NFA). Know informally GNFA and how it works.
  • For example automaton (DFA or NFA), know how to: describe it using a transition diagram, transition matrix or formal tuple notation; compute the behavior on a specific input; describe the language recognized by the automaton; prove correctness of the language recognized.
  • Know how to describe a new automata variant formally, given its informal description in words.
  • Know the definition of regular expressions, and their semantics.
  • For an example regular expression, know how to: find if a string belongs to the language defined; describe precisely the language defined by the regular expression.
• Automata Constructions:
  • Given a set of strings design a DFA/NFA/regular expression recognizing it.
  • Understand and apply to specific examples the following translations: NFA to DFA; regular expressions to NFA; DFA to regular expressions.
  • Learn to describe precisely: DFA/NFA for languages with some parameter (like alphabet size, or e.g., binary strings with 1 n positions from end); transformations on general automata (DFA/NFA) to obtain automata with some special property (like a single accept state) for the same language; transformations on general automata (NFA/DFA) to prove a closure property.
• Closure Properties:
  • Know the definitions of various operations on languages: union, intersection, complementation, concatenation, Kleene closure, homomorphic image, inverse homomorphic image. Know how to compute the result of applying these operations on example languages.
  • Understand automata/regular expression transformations used in the proofs of closure properties for regular languages.
  • Using closure properties to prove non-regularity.
  • Using closure properties to prove regularity and other closure properties.
• Non-regularity:
  • Ability to distinguish between regular and non-regular languages.
  • Ability to prove languages to be non-regular using either the lower bound proof technique, closure properties, or pumping lemma.