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

Lecture Notes on Automata Theory

DateSubjectSlidesReadings
3/30Course IntroductionPPT, PDFChapter 1
3/30Introduction to AutomataPPT, PDFSection 2.1
3/30, 4/1Deterministic Finite AutomataPPT, PDFSection 2.2
4/1, 4/6Nondeterministic Finite AutomataPPT, PDFSections 2.3 - 2.5
4/6Regular ExpressionsPPT, PDFChapter 3
4/8, 4/13Decision Properties of Regular LanguagesPPT, PDFSections 4.1, 4.3, 4.4
4/13Closure Properties of Regular LanguagesPPT, PDFSection 4.2
4/15Context-Free LanguagesPPT, PDFSection 5.1
4/15, 4/20Parse TreesPPT, PDFSections 5.2, 5.4
4/20, 4/22Normal Forms for Context-Free GrammarsPPT, PDFSection 7.1
4/22Pushdown AutomataPPT, PDFSections 6.1, 6.2
4/22, 4/27Equivalence of CFG's and PDA'sPPT, PDFSection 6.3
4/27The Pumping Lemma for Context-Free LanguagesPPT, PDFSection 7.2
4/27, 4/29Properties of Context-Free LanguagesPPT, PDFSections 7.3, 7.4
4/29, 5/6Enumerations, Turing MachinesPPT, PDFSections 8.1, 8.2
5/6, 5/11More About Turing MachinesPPT, PDFSections 8.3 - 8.6
5/13Undecidable ProblemsPPT, PDFSections 9.1, 9.2
5/13, 5/18, 5/20More Undecidable ProblemsPPT, PDFSections 9.3 - 9.5
5/20NP-CompletenessPPT, PDFSection 10.1
5/25Satisfiability, Cook's TheoremPPT, PDFSections 10.2, 10.3
5/27More NP-Complete ProblemsPPT, PDFSections 10.4, 11.1
6/1PSPACE-Complete ProblemsPPT, PDFSections 11.2, 11.3

Comments