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 cross-product 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 Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (slides)
• The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (notes) (ps) (pdf)
• Context-free grammars and context-free languages (slides)
• BNF convbnf
• BNF metabnf
• BNF pasbnf
• BNF toybnf
• Greibach normal form (slides)
• Parse Trees, and Ogden's Lemma (slides)
• Context-free grammars, context-free languages, parse trees, and Ogden's Lemma (notes) (ps) (pdf)
• Pushdown Automata and context-free 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 T-predicate, Kleene Normal Form Theorem (slides, ps) (slides, pdf)
• Elementary Recursive Function Theory, Acceptable indexings, the s-m-n 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, NP-completeness, 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