Introduction to Automata and Complexity Theory

Topic
Click to Download Slides
1.    Course Introduction
2.    Introduction to Automata
3.    Deterministic Finite Automata
4.    Nondeterministic Finite Automata
5.    Regular Expressions
6.    Decision Properties of Regular Languages
7.    Closure Properties of Regular Languages
8.    Context-Free Languages
9.    Parse Trees
10.  Normal Forms for Context-Free Grammars
11.  Pushdown Automata
12.  Equivalence of CFG's and PDA's
13.  The Pumping Lemma for Context-Free Languages
14.  Properties of Context-Free Languages
15.  Enumerations, Turing Machines
16.  More About Turing Machines
17.  Undecidable Problems
18.  More Undecidable Problems
19.  NP-Completeness
20.  Satisfiability, Cook's Theorem
21.  More NP-Complete Problems
22.  PSPACE-Complete Problems

No comments: