Introduction to the Theory of Computation, Michael Sipser, 2nd edition

Book:  Introduction to the Theory of Computation, Michael Sipser, 2^nd edition

Download Slides Here

Chapter
Introduction	0
Languages	0
Finite Automacdta, Regular Languages	1
Nondeterministic Finite Automata	1
Properties of Regular Languages Regular Expressions	1
Pumping Lemma for Regular Languages	1
More Pumping Lemma Examples	1
Review Class for Regular Languages
No class -- Presidents day
EXAM 1 on Regular Languages
Context-Free Grammars & Languages	2
Grammar Normal Forms Compilers & Parsers	2
Pushdown Automata	2
Pushdown Automata & Context-Free Lang.	2
SPRING BREAK HOLIDAYS AT RPI.	2
Turing Machines	3
Variations of Turing Machines	3
Review Class for Context-Free languages
EXAM 2 on Context-free languages
Universal Turing Machine	4
Decidable Languages Chomsky's Hierarchy	4
Undecidable Problems	4
Reductions for Decidability	5
Post-Correspondence Problem	5
Time Complexity	7
NP-Completeness – Cook’s Theorem	7
NP-Complete Reductions	7
Approximation Algorithms	9
Approximation Algorithms	9
Interactive Proofs and Probablistic Algorithm9	9

Extra Material

  Mathematical Preliminaries

  Decidable problems on Regular and Context-free languages

  Grammars for regular languages

  Deterministic pushdown automata (DPDA)

  Properties of context-free languages

  More examples of pumping lemma for context-free languages

  Other models of computation