The final exam is cumulative, so it includes all topicis covered for prelim 1 and 2; see the prelim 1 study guide and the prelim 2 study guide. Here are the additional topics covered by the final.

Automata Theory:

- Definitions:
- DFA, NFA, Regular expression
- language, language of a (DFA, NFA, RE)
- extended transition function

- Theorems:
- Kleene's theorem
- pumping lemma

Logic:

- propositional logic
- translating from English to propositional logic and back
- semantics of propositional logic
- truth tables, interpretation, entailment, validity, satisfiability

- formal deductive systems: derivations from axioms
- You will
*not*be asked to do a proof from axioms; you just have to understand the idea of a formal derivation from axioms

- You will

- first-order logic
- translating from English to first-order logic and back
- understanding the role of domains and quantification

Graph theory:

- basic notions:
- directed and undirected graph, degree, path

- graph isoomorphism
- Eulerian path
- graphs and scheduling; topological sort
- coloring, chromatic number
- bipartite graphs
- relation, equivalence relation, reflexive, symmetric, transitive