# 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
```