2D1371 Theory of Automata
Lectures
Part I. Finite Automata and Regular Languages
1. Introduction
A. Introduction, Administration
B. Lecture 2: Strings and Sets
Lecture 3: Finite Automata and Regular
Languages
Exercises: HW 1.1, 1.2, ME 2.
2. Determinization and Minimization
A. Lecture 5: Nondeterministic Finite Automata
B. Lecture 6: The Subset Construction
Exercises: HW 2.1, 2.2, ME 3, 4a, 5.
3. DFA Minimization, Automata vs. Algebraic Expressions
A. Lecture 13: DFA State Minimization
Lecture 14: A Minimization Algorithm
Exercises: HW 4.3, ME 47.
B. Lecture 8: Pattern Matching and Regular Expressions
Lecture 9: Regular Expressions and
Finite Automata
Exercises: HW 3, ME 11-20.
4. Limitations of Finite Automata
A. Lecture 11: Limitations of Finite Automata
Lecture 12: Using the Pumping Lemma
Exercises: L 12, HW 4.1, ME 35-45.
B. Lecture 15: Myhill-Nerode Relations
Lecture 16: Myhill-Nerode Theorem
Exercises: ME 55.
Part II. Pushdown Automata and Context-Free Languages
5. Context-Free Languages
A. Lecture 19: Context-Free Grammars and Languages
Lecture 20: Balanced Parentheses
B. Lecture 21: Normal Forms
Lecture 22: The Pumping Lemma for CFLs
Exercises: HW 5, ME 72, 84.
6. Pushdown Automata
A. Lecture 23: Pushdown Automata
Lecture 24: PDAs and CFGs
Exercises: HW 5.4, 6.2, 6.4, ME 76.
B. Lecture 26: Parsing
Exercises: HW 7.1.
Part III. Turing Machines and Effective Computability
7. Turing Machines
A. Lecture 28: Turing Machines and Effective
Computability
B. Lecture 29: More on Turing Machines
Exercises: HW 8.1, ME 96.
8. Decidability
A. Lecture 31: Universal Turing Machines,
Diagonalization
Lecture 32: Decidable and Undecidable
Problems
B. Lecture 33: Reduction
Lecture 34: Rice's Theorem
Exercises: HW 9.1, 9.2, 10.1, ME 106, 111.
9. Conclusion
A. Lecture 36: Other Formalisms
Lecture 37: The Lambda-Calculus
B. Lecture 38: Gödel's Incompleteness Theorem
Lecture 39: Proof of Gödel's
Incompleteness
Theorem