CIS 511, 2008

Some Course Notes and Slides

• Discrete math. basics, induction, inductive definitions
  (Chapter from ``Logic for Computer Science'', by J. Gallier)   (ps)   |  (pdf)
• Discrete mathematics for computer science
  (Book in progress, by J. Gallier)   (html)  
• Generalities, Motivations, Basics of language theory, DFA's, the cross-product construction, morphisms and maps of DFA's, NFA's   (pdf)
• NFA's, the subset construction, transducers, labeled directed graphs, regular expressions (slides)   (pdf)
• Notes on the closure definition of the regular languages (notes)   (pdf)
• The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (slides)   (pdf)
• The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (notes)   (pdf)
• Context-free grammars and context-free languages (slides)   (pdf)
• BNF convbnf
• BNF metabnf
• BNF pasbnf
• BNF toybnf
• Context-free languages as fixed points, Greibach normal form (slides)   (pdf)
• Parse Trees, and Ogden's Lemma (slides)   (pdf)
• Context-free grammars, context-free languages, parse trees, and Ogden's Lemma (notes)   (pdf)
• Pushdown Automata and context-free languages (slides)   (pdf)
• LR-parsing and shift/reduce algorithm (slides)   (pdf)
• A survey of LR-parsing methods. The graph methods for computing FIRST, FOLLOW, and LALR(1) Lookahead sets (notes)   (pdf)
• RAM programs (Post machines), Turing Machines (printed slides, pdf)
• Primitive recursive functions, partial recursive functions (printed slides, pdf)
• 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 (printed slides, pdf)   |  (slides, pdf)
• Elementary Recursive Function Theory, Acceptable indexings, the s-m-n Theorem, Undecidable Problems, K and TOTAL are not recursive, Rice's Theorem (printed slides, pdf)   |  (slides, pdf)
• Recursively Enumerable Sets, Many-One Reducibility, Complete Sets, TOTAL, FINITE, and their complements, are not r.e. (printed slides, pdf)   |  (slides, pdf)
• The Recursion Theorem, the Extended Rice Theorem, Productive and Creative Sets (printed slides, pdf)   |  (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, pdf)
• 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) (pdf)
• Theory of Computation in German! (slides)
• Book Manuscript, by Gallier and Hicks

Back to Gallier Homepage

published by:

Jean Gallier