CSE 262, Fall, 2004
Automata, Computability and Complexity
Some Course Notes and Slides

Discrete math. basics, induction, inductive definitions
(Chapter from ``Logic for Computer Science'', by J. Gallier)
(ps)

(pdf)
 Generalities, Motivations, Basics of language theory,
DFA's, the crossproduct construction, morphisms and maps
of DFA's, NFA's (slides)
(ps)

(pdf)
 NFA's,
the subset construction,
transducers, labeled directed graphs, regular expressions (slides)

Notes on the closure definition of the regular languages (notes)
(ps)
(pdf)
 The MyhillNerode
Theorem. State Equivalence, and minimization of DFA's (slides)

The MyhillNerode
Theorem. State Equivalence, and minimization of DFA's (notes)
(ps)
(pdf)

Contextfree
grammars and contextfree languages (slides)

BNF convbnf

BNF metabnf

BNF pasbnf

BNF toybnf

Greibach normal form (slides)
 Parse Trees,
and Ogden's Lemma (slides)

Contextfree grammars,
contextfree languages, parse trees, and Ogden's Lemma (notes)
(ps)
(pdf)
 Pushdown Automata
and contextfree languages (slides)
(ps)
 RAM programs (Post machines), Turing Machines
(slides, ps)
 Primitive recursive functions, partial recursive functions
(slides, ps)
 RAM programs (Post machines), Turing Machines,
Primitive recursive functions, partial recursive functions
(slides, pdf)
 Coding of RAM programs, Unsolvability of the Halting Problem, A universal RAM program,
The Enumeration Theorem, Kleene's Tpredicate, Kleene Normal Form Theorem
(slides, ps)
(slides, pdf)
 Elementary Recursive Function Theory, Acceptable indexings, the smn Theorem,
Undecidable Problems, K and TOTAL are not recursive, Rice's Theorem
(slides, ps)
(slides, pdf)
 Computational Complexity, the class P, satisfiability,
the class NP, NPcompleteness, Cook's theorem
(printed slides, pdf)
(slides, pdf)
 Eulerian and Hamiltonian cycles
(slides, ps)

Prove that P = NP, and get a one million dollar reward!
(Clay Institute)

Computability, Undecidability, and Basic
Recursive Function Theory (notes)
(ps)
(pdf)

Book Manuscript, by Gallier and Hicks
Relevant Fun Software
Jflap