CIS 262, Spring 2020

Some Course Notes and Slides

Slides

• Motivations, Questions (slides)   (pdf)
• Basics of language theory. Generalities, Motivations,
  Strings, Concatenation, Languages, Language operations (slides)   (pdf)
• DFA's, the cross-product construction, NFA's,
  the Rabin and Scott Construction (slides)   (pdf)
• Transducers; an application of NFA's: text search (slides)   (pdf)
• Hidden Markov Models (HMMs) (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)
• Gorn Trees, A strong pumping lemma for CFL's: Ogden's Lemma (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)
• Undecidability of the Halting Problem and Universal RAM Programs
  Undecidability and Reducibility (slides)   (pdf)
• Listable Sets and Diophantine Sets; Hilbert's Tenth Problem (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
  Languages, Automata, Grammars
  Some Notes for CIS262 (pdf)
• Introduction to the Theory of Computation
  Computability, Complexity, and the Lambda Calculus
  Some Notes for CIS262 (pdf)
• Proofs, Computability, Complexity
  And the Lambda Calculus
  An Introduction (pdf)
• Chapters 1, 2, 3 on Mathematical Reasoning and Logic, functions, relations,
  from "Discrete Mathematics, Second Edition:" (pdf)
• Discrete mathematics.
  (Springer UTX, J. Gallier)   (html)  
• Discrete math. basics, induction, inductive definitions
  (Chapter from ``Logic for Computer Science'', by J. Gallier)   (pdf)
• 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".
  Sections 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

published by:

Jean Gallier