CIS 511, Spring 2004
Introduction to the Theory of Computation
Some Course Notes and Slides

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

Generalities, Motivations, Basics of language theory,
DFA's, the crossproduct construction, morphisms and maps
of DFA's, NFA's (slides)
 NFA's,
the subset construction,
transducers, labeled directed graphs, regular expressions (slides)

Notes on the closure definition of the regular languages (notes)
(ps)
(pdf)
 The MyhillNerode
Theorem. State Equivalence, and minimization of DFA's (slides)

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

Contextfree
grammars and contextfree languages (slides)

BNF convbnf

BNF metabnf

BNF pasbnf

BNF toybnf

Contextfree languages as fixed points, Greibach normal form (slides)
 Parse Trees,
and Ogden's Lemma (slides)

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

LRparsing and shift/reduce algorithm (slides)
 A survey of
LRparsing methods. The graph methods for computing FIRST, FOLLOW,
and LALR(1) Lookahead sets (notes)
 RAM programs (Post machines), Turing Machines
(slides, ps)
 Primitive recursive functions, partial recursive functions
(slides, ps)
 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, ps)
(slides, pdf)
 Elementary Recursive Function Theory, Acceptable indexings, the smn Theorem,
Undecidable Problems, K and TOTAL are not recursive, Rice's Theorem
(slides, ps)
(slides, pdf)
 Recursively Enumerable Sets, ManyOne Reducibility, Complete Sets,
TOTAL, FINITE, and their complements, are not r.e.
(slides, ps)
(slides, pdf)
 The Recursion Theorem, the Extended Rice Theorem, Productive and Creative Sets
(slides, ps)
(slides, 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, NPcompleteness, Cook's theorem
(printed slides, pdf)
(slides, pdf)
 Eulerian and Hamiltonian cycles
(slides, ps)

Prove that P = NP, and get a one million dollar reward!
(Clay Institute)
 Phrase structure grammars, contextsensitive grammars
(printed slides, pdf)

Computability, Undecidability, and Basic
Recursive Function Theory (notes)
(ps)
(pdf)

Book Manuscript, by Gallier and Hicks