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.