DD2371 Automata Theory
- Course Outline -
Below, "Lecture X" refers to the chapter with this name in the course
book, exercise "HW n.m" refers to problem 'm' of Homework 'n' in the
course book, and exercise "ME n" refers to Miscellaneous exercise 'n'
in the course book.
Class 1 [Lectures: 1, 2]
- Introduction to Automata Theory
- Course goals and syllabus
- Course organization and administration
- First definitions
Part I: Finite
Automata and Regular
Languages
Class 2 [Lectures: 3, 4] [Exercises: HW 1.1, 1.2; ME 2]
- Deterministic finite automata (DFA)
- Regular languages
- Complement construction
- Product construction
- Closure properties of regular languages
Class 3 [Lectures: 5, 6] [Exercises: HW 2.1, 2.2; ME 4(a), 5,
6, 10(a,b)]
- Nondeterministic finite automata (NFA)
- From DFA to NFA
- From NFA to DFA
- NFAs with epsilon transitions
- More closure properties of regular languages
Class 4 [Lectures: 8, 9, A] [Exercises: HW 3.1(a,b); ME 11(b)]
- Regular expressions (RE)
- From RE to NFA
- From NFA to RE
- Kleene algebra
Class 5 [Lectures: 13, 14] [Exercises: HW 4.3, ME 47]
Class 6 [Lectures: 15, 16, 11, 12] [Exercises: HW 4.1; ME 55,
6, 35-45]
- Myhill-Nerode Relations and Theorem
- NFAs are exponentially more succinct than DFAs (cf. ME 6, p. 317)
- The Pumping Lemma for regular languages
Class 7
- Proving non-regularity using the Pumping Lemma
- Proving non-regularity using reduction
- Cantor's Theorem and limitations of Finite Automata
- Summary of Part I
- Handing out Assignment I
Part II:
Pushdown Automata and
Context-Free Languages
Class 8 [Lectures: 19, G]
- Introduction to Part II
- Context-free grammars and languages
- Context-free languages subsume regular languages
- Chomsky-Schützenberger Theorem
Class 9 [Lectures: 20-22] [Exercises: HW 5.2, 5.3; ME 76(a)]
- Proving correctness of grammars: Balanced parentheses
- Chomsky and Greibach normal forms
- Pumping Lemma for CFLs
Class 10 [Lectures: 23-24, E] [Exercises: HW 5.4; ME 76(b)]
- Pushdown automata
- Acceptance on empty stack versus on final states
- From CFG in GNF to NPDA with one control state
Class 11 [Lectures: F, 27(pp.195-197)] [Exercises: HW 7.2]
- Closure properties of CFLs
- Deterministic PDAs
- Application: Control flow analysis of programs
- Summary of Part II
- Handing out Assignment II
Part III:
Turing Machines and Effective
Computability
Class 12 [Lectures: 28-30] [Exercises: HW 8.1; ME 96]
- Introduction to Part III
- Effective computability and models of computation
- Turing machines
- Equivalent models
Class 13 [Lectures: 31]
- A Universal Turing machine
- Self-reference and incompleteness
- Undecidability of the Halting problem
- Diagonalization and reduction
- Handing out Assignment III
Class 14 [Lectures: 32-34, 37] [Exercises: HW 9.1, 9.2; ME
106,
111]
- Decidable and undecidable problems
- Rice's theorem
- Other formalisms: The Lambda calculus
Class 15
- Course Summary
- Exam Preparation
- Assignments discussion
- Course Evaluation