This page contains both fixed and changing information concerning material to be covered and due dates. Topics are followed by relevant sections in the textbook. All handout dates, due dates, and test dates are fixed. All other listings are subject to minor changes.
administration, strings, languages, induction, recursive definitions [1, 3.1.1, Theorem 3.11, supplement on introductory material]
DFAs [2.1 (skip if you find it confusing), 2.2], NFAs [2.3.1-2.3.4], epsilon-NFAs [2.5.1-2.5.4]
Assignment handed out by January 11
regular expressions [3.1], equivalence of finite automata with each other and regular expressions [2.3.5-2.3.6; 2.5.5; 3.2; supplement on Kleene's theorem]
Problem session 1 on January 20
closure properties for regular languages [4.2.1-4.2.2; supplement on closure property proof recipes], pumping lemma for regular languages [4.1], decision problems for regular languages [supplement on decision problems for regular languages, 4.3]
context-free languages [5.1, supplement on equivalence of languages], derivations [5.2], ambiguity [5.4]
Problem session 2 on February 4
derivations [5.2], ambiguity [5.4], normal forms [7.1]
pushdown automata [6.1-6.2]
deterministic PDAs [6.4.1], equivalence of PDAs and CFLs [6.3]
Problem session 3 on March 3
pumping lemma for CFLs [7.2], closure properties for CFLs [7.3, supplement on context-free languages]
decision problems for CFLs [supplement on context-free languages, 7.4]; Turing machines, recursive and r.e [supplement on Turing machines, 8.1-8.3]
Test 2 March 15 during class time
computation of functions, multiple tracks [8.3.2], multitape Turing machines [8.4.1, 8.4.2], nondeterminism in Turing machines [8.4.4], restrictions on Turing machines [8.5]
Universal Turing machines [9.2.3], properties of recursive and r.e. languages [9.2.1, 9.2.2, 9.2.4], languages that are not recursive [9.2.4, 9.3.1, 9.3.2], languages that are not r.e. [9.1]