# Some Course Notes and Slides

## Slides

• Generalities, Motivations, Basics of language theory,
DFA's, the cross-product construction, NFA's,
the Rabin and Scott Construction (slides)   (pdf)
• NFA's and Regular expressions (slides)   (pdf)
• The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (slides)   (pdf)
• Context-free Grammars. Chomsky Normal Form. Regular Languages are context-free. (slides)   (pdf)
• The Greibach Normal Form and Least Fixed Points (slides)   (pdf)
• Gorn Trees, A strong pumping lemma for CFL's: Ogden's Lemma (slides)   (pdf)
• Pushdown Automata (slides)   (pdf)
• An Introduction to LR-parsing. Knuth's construction of an LR(0) parser. (slides)   (pdf)
• BNF convbnf
• BNF metabnf
• BNF pasbnf
• BNF toybnf
• RAM Programs, Turing Machines, and the Partial Recursive Functions (slides) (pdf)
• The Primitive Recursive Functions and the Partial Recursive Functions (slides)   (pdf)
• The Puccini Theorem (slides)   (pdf)
• Universal RAM Programs and the Undecidability of the Halting Problem
Undecidability and Reducibility (slides)   (pdf)
• Elementary Recursive Function Theory (slides)   (pdf)
• The Post Correspondence Problem. Applications to Undecidability Results (slides)   (pdf)
• Computational Complexity; P and NP (slides)   (pdf)
• Some NP-Complete Problems (slides)   (pdf)

• Prove that P = NP, and get a one million dollar reward! (Clay Institute)
• Theory of Computation in German! (slides)

## Notes

• Introduction to the Theory of Computation
Some Notes for CIS511 (pdf)
• Chapters 1, 2, 3 on Mathematical Reasoning and Logic, functions, relations,
from "Discrete Mathematics, Second Edition:" (pdf)
• Discrete math. basics, induction, inductive definitions
(Chapter from ``Logic for Computer Science'', by J. Gallier)   (pdf)
• Discrete mathematics.
(Springer UTX, J. Gallier)   (html)
• RAM Programs, Turing Machines, and the Partial Recursive Functions (notes) (pdf)
• The Kleene-Herbrand-Godel Computable Functions (notes) (pdf)
• Chapter 5 of " Discrete Mathematics. Some Notes".
Especially Sections 5.1, 5.3, 5.4, 5.9, 5.10, 5.11 and 5.12
Notes on Public Key Cryptography and RSA   (pdf)
• Notes on Public Key Cryptography and Primality Testing
Part 1: Randomized Algorithms Miller-Rabin and Solovay-Strassen Tests (pdf)
• Book Manuscript, by Gallier and Hicks (pdf)
• Definitions of terms such as "Theorem, Lemma, Proposition, etc.",
from Legendre's "Elements de Geometrie" (first publication, 1794)   (pdf)
• A Turing Machine in the classic style (html)
• Preface by Martin Davis of "Hilbert's Tenth Problem",
by Yuri Matiyasevich   (pdf)

Back to Gallier Homepage