Theoretical Computer Science Exam #1 Review

Sets

   definition, listing elements, empty set, singleton
   finite vs. infinite sets, equinumerous, countable, countably infinite
   N, N+, Q, R, C
   set operations
      element of, union, intersection, subtraction, subset or equal
      proper subset, equal disjoint
      Cartesian product, power set, cardinality, partition
   set properties
      idempotency, commutativity, associativity, distributivity
      absorption, DeMorgan's Laws

Relations

   definition, binary relation, ordered n-tuple, sequence
   properties of binary relations
      reflexive, symmetric, anti-symmetric, transitive
      equivalence relation, equivalence class
   composition
   chain, cycle, trivial vs. nontrivial cycles
   partial order, total order, minimal elements
   closure, closure property
   reflexive, transitive closure

Functions

   definition, domain, range, image, one-to-one, onto, bijection

Proof Techniques

   proof by induction, base case, inductive hypothesis, inductive step
   pigeonhole principle

Languages

   symbol, alphabet, string, language, substring, prefix, suffix
   concatenation, union, Kleene closure
   language generator, language recognition device

Regular Languages

   regular expressions, language denoted by a regular expression
   finite state machines, DFA, NFA, NFA with epsilon-transitions
   transition rules, start state, final state, string acceptance
   state diagram, configuration
   yields in one step, yields in any number of steps
   the language accepted by a machine
   equivalence of techniques
      DFA -> NFA
      NFA -> DFA
      NFA -> NFA with epsilon transition
      NFA with epsilon transition -> NFA
      RE -> NFA with epsilon transition
      DFA -> RE
   proving a language to be regular or not regular
      pumping lemma
      closures, union, concatenation, Kleene closure
      complement, intersection, quotient
   DFA state minimization, distinguishable states, equivalent states
   reachable states, Myhill-Nerode Theorem

Context-Free Languages

   relation to regular languages
   rewrite rule, terminal symbol, nonterminal symbol, context-free grammar
   ->G, =>G, language generated by G
   derivation, length of a derivation, number of steps in a derivation