Computer Science Dartmouth College 
Computer Science 39 
Winter 2009 
This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata, regular languages, contextfree languages, pushdown automata, Turing machines, computability, and NPcompleteness.
This course has substantial mathematical content. It is expected that a student who enrols for this course already knows how to write mathematical proofs and is generally mathematically mature. If a student passes this basic criterion and is interested in thinking philosophically about what a computer can or cannot do, then this course should be great fun.
Lectures 
Kemeny 008  11 hour  MonWedFri 11:1512:20, Xhr Tue 12:0012:50 
Instructor 
Amit Chakrabarti  Sudikoff 107  61710  Office hours: Mon 18:0020:00, Fri 15:0016:30, or by appointment 
Teaching Assistants 
Qi (Tracy) Gu  Sudikoff 220  68752 
Office hours: Fri 16:0018:00
Grace Moy  Sudikoff 114  4405540373  Office hours: Sun 16:0018:00 William HendersonFrost  Sudikoff 114  8177016019  Office hours: Mon 16:0018:00 
Textbook 
Required: "Introduction to the Theory of Computation," Second Edition. Michael Sipser. Suggested additional reading (not required): "Introduction to Automata Theory, Languages and Computation." J. E. Hopcroft and J. D. Ullman. 
Prerequisites 
CS 25, or a strong mathematics backround and permission of the instructor 
Work 
One homework per week. [35 points] Two inclass quizzes. [15 points] One takehome midterm. [20 points] One takehome final exam. [30 points] Please take note of the late homework policy. It will be enforced, strictly. 
This schedule will be updated frequently. Please check back often, and please remember to hit the RELOAD button to get the latest schedule.
Any part of the schedule that is greyed out is tentative and subject to change.
Lecture Number 
Reading Due 
Homework 
Topics Covered in 

Week 1 
1  Jan 5  —  —  Welcome, administrivia, overview; Mathematical notation (slides) 
2  Jan 6 (Xhr)  0.1, 0.2, 0.3  —  Types of proof: by construction, by contradiction, by induction (slides)  
3  Jan 7  0.4  —  Strings and languages; Finite automata; DFA examples (slides)  
4  Jan 9  1.1 up to p34  — 
Formal definition of DFA as (Q,Σ,δ,q_{0},F);
More DFA examples


Week 2 
5  Jan 12  1.1  — 
NFA introduced; Examples; Formalization of NFAs and DFA/NFA
computation

6  Jan 13 (Xhr)  —  — 
More on NFAs; The union, concatenation and Kleene star operations


7  Jan 14  —  HW1 
Regular expressions, examples, conversion to NFA
(lecture notes)


8  Jan 16  1.3 up to p69  — 
Equivalence of DFAs, NFAs and regular expressions, I


Week 3 
Jan 19  —  — 
No lecture: MLK Day 

9  Jan 20 (Xhr)  1.2  — 
Equivalence of DFAs, NFAs and regular expressions, II
(lecture notes)


10  Jan 21  1.3  HW2 
The pumping lemma and proofs of nonregularity 

11  Jan 23  1.4  — 
More proofs of nonregularity; Proof of the pumping lemma


Week 4 
12  Jan 26  —  — 
Closure properties of regular languages (guest lecture) 
Jan 27 (Xhr)  Chapter 1  — 
Open/Review session with TAs 

Jan 28  —  HW3 
Quiz 1: closednotes, inclass 

13  Jan 30  —  — 
Pushdown automata; Examples of PDAs 

Week 5 
14  Feb 2  —  — 
Formal definition of a PDA; More examples 
15  Feb 3 (Xhr)  2.2 up to p115  — 
Closure under union, concatenation and Kleene star;
ContextFree Grammars (CFGs); Basic examples


16  Feb 4  2.1 up to p105  HW4 
More advanced CFGs: N_{0} = N_{1} and nonxx
strings (lecture notes)


17  Feb 6  —  — 
Equivalence of CFGs and PDAs, I: PDA to CFG 

Week 6 
18  Feb 9  —  — 
Equivalence of CFGs and PDAs, II: CFG to PDA
(lecture notes)

Feb 10 (Xhr)  2.2  — 
Open/Review session with TAs 

19  Feb 11  —  Midterm 
Chomsky Normal Form; Conversion Algorithm; Pumping lemma for CFLs
(guest lecture) 

Feb 13  —  — 
No lecture: Winter Carnival


Week 7 
20  Feb 16  2.3  — 
Applications of CFL pumping lemma; Closure properties 
21  Feb 17 (Xhr)  Chapter 2  — 
Turing machines; formal description; demos
(palindromes,
adder)


22  Feb 18  3.1  — 
Deciders/recognizers; Multitape TMs and their equivalence with TMs
(slides) 

23  Feb 20  —  HW5 
Nondeterministic TMs; the RAM model; ChurchTuring Thesis
(slides) 

Week 8 
24  Feb 23  3.2 up to p150  — 
Enumerator TMs; Decision problems for the major language classes:
A_{DFA}, A_{CFG} and A_{TM} 
25  Feb 24 (Xhr)  Chapter 3  —  Decidability of A_{DFA}, A_{CFG};
Recognizability of A_{TM}; Undecidability of A_{TM};
Unrecognizability of
A_{TM}


26  Feb 25  4.1  HW6 
Reductions; Decidability of E_{DFA},
ALL_{DFA}, EQ_{DFA}, E_{CFG};
Unrecognizability of E_{TM} 

Feb 27  Chapter 4  — 
Quiz 2: closednotes, inclass 

Week 9 
27  Mar 2  5.1 up to p192; 5.3  — 
Time complexity, P and NP 
28  Mar 3 (Xhr)  7.1  — 
NPcompleteness and polynomial time reductions
(slides) 

29  Mar 4  7.1 – 7.3  HW7 
More NPcompleteness proofs 

30  Mar 6  —  — 
Computation tableaux; The CookLevin theorem 

Week 10 
31  Mar 9  —  — 
CookLevin theorem continued; Unrecognizability of ALL_{CFG}

32  Mar 10 (Xhr)  7.4 up to p276; 7.5  HW8 (optional) 
Wrapup 

Mar 16  Takehome 48hour The final exam webpage is now closed. 
If you are a registered student, you may verify your grades as entered in our database using the form below.