## - 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
• First definitions

#### 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]

• DFA state minimization

#### 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

#### 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

#### 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