CIS 511, 2010
Some Course Notes and Slides
Notes

Discrete math. basics, induction, inductive definitions
(Chapter from ``Logic for Computer Science'', by J. Gallier)
(ps) 
(pdf)

Discrete mathematics. Some Notes
(Book in progress, by J. Gallier)
(html)

Notes on the closure definition of the regular languages (notes)
(pdf)

The MyhillNerode
Theorem. State Equivalence, and minimization of DFA's (notes)
(pdf)

Contextfree grammars,
contextfree languages, parse trees, and Ogden's Lemma (notes)
(pdf)

A survey of LRparsing methods. The graph methods for
computing
FIRST, FOLLOW,
and LALR(1) Lookahead sets (notes)
(pdf)

Computability, Undecidability, and Basic
Recursive Function Theory (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)

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)

Preface by Martin Davis of "Hilbert's Tenth Problem",
by Yuri Matiyasevich
(pdf)

Theory of Computation in German!
(slides)
Slides
 Generalities, Motivations, Basics of language theory,
DFA's, the crossproduct construction,
morphisms and maps
of DFA's, NFA's, the subset construction
(pdf)

Transducers, labeled directed graphs, regular expressions (slides)
(pdf)
 The MyhillNerode
Theorem. State Equivalence, and minimization of DFA's (slides)
(pdf)
 Contextfree
grammars and contextfree languages (slides)
(pdf)

BNF convbnf

BNF metabnf

BNF pasbnf

BNF toybnf
 Contextfree languages as fixed points,
Greibach normal form (slides)
(pdf)
 Parse Trees, and Ogden's Lemma (slides)
(pdf)
 Pushdown Automata
and contextfree languages (slides)
(pdf)
 LRparsing and shift/reduce algorithm (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 Tpredicate, Kleene Normal Form Theorem
(slides, pdf)
 Elementary Recursive Function Theory, Acceptable indexings,
the smn Theorem,
Undecidable Problems,
K and TOTAL are not recursive, Rice's Theorem
(slides, pdf)
 Recursively Enumerable Sets, ManyOne Reducibility, Complete Sets,
TOTAL, FINITE, and their complements, are not r.e.
(slides, pdf)
 The Recursion Theorem, the Extended Rice Theorem,
Productive and Creative Sets
(slides, pdf)
 The Post Correspondence Problem (PCP), Undecidable properties of
languages, Greibach's theorem
(slides, pdf)
 Computational Complexity, the class P, satisfiability,
the class NP, NPcompleteness, Cook's theorem
(slides, pdf)
 Eulerian and Hamiltonian cycles
(slides, pdf)

Prove that P = NP, and get a one million dollar reward!
(Clay Institute)

Notes on Public Key Cryptography and RSA (slides)
(pdf)

What is a proof? (Talk given on November 6, 2008)
slides (pdf)
slides (keynote)

A Turing Machine in the classic style
(html)
Slides, Printed Version
 RAM programs (Post machines), Turing Machines
(printed slides, pdf)
 Primitive recursive functions, partial recursive functions
(printed slides, pdf)
 Coding of RAM programs, Unsolvability of the Halting Problem,
A universal RAM program,
The Enumeration Theorem, Kleene's Tpredicate, Kleene Normal Form Theorem
(printed slides, pdf)
 Elementary Recursive Function Theory, Acceptable indexings,
the smn Theorem,
Undecidable Problems,
K and TOTAL are not recursive, Rice's Theorem
(printed slides, pdf)
 Recursively Enumerable Sets, ManyOne Reducibility, Complete Sets,
TOTAL, FINITE, and their complements, are not r.e.
(printed slides, pdf)
 The Recursion Theorem, the Extended Rice Theorem,
Productive and Creative Sets
(printed slides, pdf)
 The Post Correspondence Problem (PCP), Undecidable properties of
languages, Greibach's theorem
(printed slides, pdf)
 Computational Complexity, the class P, satisfiability,
the class NP, NPcompleteness, Cook's theorem
(printed slides, pdf)
 Phrase structure grammars, contextsensitive grammars
(printed slides, pdf)
Back to
Gallier Homepage
published by: