Lecture Notes on Automata Theory
Date | Subject | Slides | Readings |
---|---|---|---|
3/30 | Course Introduction | PPT, PDF | Chapter 1 |
3/30 | Introduction to Automata | PPT, PDF | Section 2.1 |
3/30, 4/1 | Deterministic Finite Automata | PPT, PDF | Section 2.2 |
4/1, 4/6 | Nondeterministic Finite Automata | PPT, PDF | Sections 2.3 - 2.5 |
4/6 | Regular Expressions | PPT, PDF | Chapter 3 |
4/8, 4/13 | Decision Properties of Regular Languages | PPT, PDF | Sections 4.1, 4.3, 4.4 |
4/13 | Closure Properties of Regular Languages | PPT, PDF | Section 4.2 |
4/15 | Context-Free Languages | PPT, PDF | Section 5.1 |
4/15, 4/20 | Parse Trees | PPT, PDF | Sections 5.2, 5.4 |
4/20, 4/22 | Normal Forms for Context-Free Grammars | PPT, PDF | Section 7.1 |
4/22 | Pushdown Automata | PPT, PDF | Sections 6.1, 6.2 |
4/22, 4/27 | Equivalence of CFG's and PDA's | PPT, PDF | Section 6.3 |
4/27 | The Pumping Lemma for Context-Free Languages | PPT, PDF | Section 7.2 |
4/27, 4/29 | Properties of Context-Free Languages | PPT, PDF | Sections 7.3, 7.4 |
4/29, 5/6 | Enumerations, Turing Machines | PPT, PDF | Sections 8.1, 8.2 |
5/6, 5/11 | More About Turing Machines | PPT, PDF | Sections 8.3 - 8.6 |
5/13 | Undecidable Problems | PPT, PDF | Sections 9.1, 9.2 |
5/13, 5/18, 5/20 | More Undecidable Problems | PPT, PDF | Sections 9.3 - 9.5 |
5/20 | NP-Completeness | PPT, PDF | Section 10.1 |
5/25 | Satisfiability, Cook's Theorem | PPT, PDF | Sections 10.2, 10.3 |
5/27 | More NP-Complete Problems | PPT, PDF | Sections 10.4, 11.1 |
6/1 | PSPACE-Complete Problems | PPT, PDF | Sections 11.2, 11.3 |
Comments
Post a Comment