Book in progress (2009)

- By downloading these files you are agreeing to
the following conditions of use: Copyright 2003 by Jean Gallier. This
material may be reproduced for any educational purpose, multiple copies
may be made for classes, etc. Charges, if any, for reproduced copies must
be no more than enough to recover reasonable costs of reproduction. Reproduction
for commercial purposes is prohibited. The cover page, which contains
these terms and conditions, must be included in all distributed copies.
**It is not permitted to post this book for downloading in any other web location**, though links to this page may be freely given. - 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)
- The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (notes) (pdf)
- Context-free grammars, context-free languages, parse trees, and Ogden's Lemma (notes) (pdf)
- Pushdown Automata and context-free languages (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)
- Computability, Undecidability, and Basic Recursive Function Theory (notes) (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)
- Phrase structure grammars, context-sensitive grammars (printed slides, pdf)

Back to Gallier's books (complete list)

Back to Gallier Homepage