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)
- 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
- Context-free languages as fixed points, 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) (pdf)
-
LR-parsing and shift/reduce algorithm (slides)
- A survey of
LR-parsing methods. The graph methods for computing FIRST, FOLLOW,
and LALR(1) Lookahead sets (notes)
- 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)
- Recursively Enumerable Sets, Many-One Reducibility, Complete Sets, TOTAL, FINITE, and their complements, are not r.e. (slides, ps) (slides, pdf)
- The Recursion Theorem, the Extended Rice Theorem, Productive and Creative Sets (slides, ps) (slides, pdf)
- The Post Correspondence Problem (PCP), Undecidable properties of languages, Greibach's theorem (printed slides, pdf) (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)
- Phrase structure grammars, context-sensitive grammars (printed slides, pdf)
-
Computability, Undecidability, and Basic
Recursive Function Theory (notes)
(ps)
(pdf)
-
Book Manuscript, by Gallier and Hicks