Date |
Description |
Textbook References |
May 17 |
Introduction to automata theory and some background
[Slides ] |
Hopcroft, Motwani, and Ullman: Chapter 1 –or– Sipser: Chapter 1 |
May 21 |
Finite Automata and their properties [Slides] |
Hopcroft, Motwani, and Ullman: Section 2.1, 2.2, and 2.3 –or– Sipser: Section 1.1 |
May 22 |
Tutorial class—no new concepts were introduced. |
May 24 |
Nondeterminism and Alternation [Slides] |
Hopcroft, Motwani, and Ullman: Section 2.3, 2.4, 2.5, and 4.2–or–Sipser: Section 1.2 |
May 28 |
Regular Expressions [Slides] |
Hopcroft, Motwani, and Ullman: Chapter 3–or–Sipser: Section 1.3 |
May 29 |
Tutorial class—no new concepts were introduced. |
|
May 31 |
Lecture postponed to June 3rd. |
|
June 3 |
Pumping Lemma, Minimization, and Myhill-Nerode Theorem [Slides] |
Hopcroft, Motwani, and Ullman: Chapter 4–or–Sipser: Section 1.4 |
June 4 |
Definition of Turing machines, examples, variants, the Church Turing thesis [Slides] |
Hopcroft, Motwani, and Ullman: Chapter 8–or–Sipser: Chapter 3 |
June 5 |
Tutorial class—no new concepts were introduced. Quiz. |
|
June 7 |
Decidability (recursive) and Turing recognizability (r.e),
Undecidable languages (the Halting problem), and some more properties of decidable and
r.e languages [Slides] |
Hopcroft, Motwani, and Ullman: Chapter 9 –or–Sipser:Chapter 4 |
June 10 |
Reductions, more undecidable problems, PCP, and counter machine [Slides] . |
|
June 11 |
Tutorial class |
|
June 12 |
Mid-Semester Exam. |
|
June 18 |
Pushdown automata (PDA), acceptance by final states and empty stack, non-deterministic and deterministic PDA,
Introduction to context free grammars (CFG)
|
|
June 19 |
More on context free grammars, tutorial |
|