BS edu: Computer Science: 4th Semester: Book Automata Theory

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