CIS 511, Spring 2021

Some Course Notes and Slides

Motivations, Problems (slides) (pdf)
Generalities, Motivations, Basics of language theory (slides) (pdf)
DFA's, the cross-product construction, NFA's,
the Rabin and Scott Construction (slides) (pdf)
Finite state transducers, Text search (slides) (pdf)
Hidden Markov Models (HMM's) (slides) (pdf)
Regular languages and regular expressions (slides) (pdf)
Regular languages and right-invariant equivalence relations.
The Myhill-Nerode theory. Minimal DFA's and algorithms to find them (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)
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 and Turing Machines (slides) (pdf)

The Primitive Recursive Functions and the Partial Computable 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 Lambda Calculus as a Computation Model (slides) (pdf)

Recursion Theory: More Advanced Topics (slides) (pdf)

Listable and Diopantine Sets; Hilbert's Tenth (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)

Polynomial-Space Complete Problems; PS and NPS (slides) (pdf)

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

Theory of Computation in German! (slides)

Introduction to the Theory of Computation
Languages, Automata, and Grammars
Some Notes for CIS511 (pdf)
Introduction to the Theory of Computation
Computability, Complexity, and the Lambda Calculus
Some Notes for CIS511 (pdf)
Proofs, Computability, Undecidability, Complexity, and the Lambda Calculus
An Introduction (book in progress) (pdf)
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)

published by: