Computer Science Dartmouth College 
Computer Science 39 
Fall 2006 
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 
Sudikoff 214  12 hour  MWF 12:3013:35, Xhr T 13:0013:50 
Instructor 
Amit Chakrabarti  Sudikoff 107  61710  Office hours: Mon & Fri 10:0011:30 or by appointment 
Teaching Assistants 
Vibhor Bhatt  Sudikoff 221  68753 
Office hours: Tue 15:0017:00, Sun 18:0019:00 or by appointment
Hong Lu  Sudikoff 062  6????  Office hours: Mon 19:0021:00, Sun 19:0020:00 or by appointment 
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.
L# 
Date 
Reading Due 
Homework Due 
Class Topic 
1  Sep 20  —  —  Welcome, administrivia, overview; Mathematical notation (slides) 
2  Sep 22  0.1, 0.2, 0.3  —  Types of proof: by construction, by contradiction, by induction (slides) 
3  Sep 25  0.4  —  Strings and languages; Finite automata introduced (slides) 
4  Sep 26 (Xhr)  1.1 up to p34  — 
More on (deterministic) finite automata; examples of DFAs;
thirdlastchar challenge

5  Sep 27  1.1  — 
Formal definition of DFA as (Q,Σ,δ,q_{0},F);
DFA computation formalized 
6  Sep 29  —  — 
NFA introduced; Examples; Formalization of NFAs and NFA computation

7  Oct 2  —  — 
Designing NFAs; Union and concatenation of two regular languages
is regular 
8  Oct 3 (Xhr)  —  — 
Kleene star; Regular expressions and examples 
9  Oct 4  1.3 up to p66  HW1 
Equivalence of DFAs, NFAs and regular expressions, I 
10  Oct 6  1.2  — 
Equivalence of DFAs, NFAs and regular expressions, II 
11  Oct 9  1.3  — 
Equivalence of DFAs, NFAs and regular expressions, III
(lecture notes)

12  Oct 10 (Xhr)  —  — 
Example of DFA to RegExp conversion; The pumping lemma 
13  Oct 11  —  HW2 
Proof and applications of the pumping lemma 
Oct 13  No lecture; homecoming  
14  Oct 16  Chapter 1  — 
Closure properties of regular languages 
Oct 17 (Xhr)  —  — 
Quiz 1: closednotes, inclass 

15  Oct 18  —  HW3 
Pushdown automata (PDAs); Examples 
Oct 20  —  — 
More examples of PDAs and a formal definition


16  Oct 23  2.2  — 
Closure of contextfree languages under union, concatenation
and Kleene star (Vibhor)

17  Oct 24 (Xhr)  —  — 
Closure and nonclosure properties;
a PDA for notww (Vibhor) 
18  Oct 25  —  HW4 
Contextfree grammars; Simple examples 
19  Oct 27  —  — 
CFGs formalized; a CFG for equally many 0s and 1s
(lecture notes)

20  Oct 30  2.1  — 
Equivalence of CFGs and PDAs, I: PDA to CFG 
21  Oct 31 (Xhr)  —  — 
Equivalence of CFGs and PDAs, II: CFG to PDA
(lecture notes)

22  Nov 1  2.2 (again)  Midterm 
Pumping lemma for contextfree languages; Applications

23  Nov 3  2.3  — 
Chomsky Normal Form; Proof of the pumping lemma for CFLs 
24  Nov 6  Chapter 2  — 
Turing machines; Informal description and simple examples 
25  Nov 7 (Xhr)  3.1  — 
Two TM applets; formal definition of a TM

26  Nov 8  —  HW5 
Deciders/recognizers; Multitape TMs and their equivalence with TMs
(slides) 
27  Nov 10  3.2 up to p138  — 
Nondeterministic TMs; the RAM model; ChurchTuring Thesis
(slides) 
28  Nov 13  Chapter 3  — 
Enumerator TMs; Decision problems for the major language classes:
A_{DFA}, A_{CFG} and A_{TM} 
Nov 14 (Xhr)  —  — 
Quiz 2: closednotes, inclass 

29  Nov 15  4.1  HW6  Decidability of A_{DFA}, A_{CFG};
Recognizability of A_{TM}; Undecidability of A_{TM}
and the halting problem

30  Nov 17  4.2 up to p180  —  Decidability of E_{DFA},
ALL_{DFA}, EQ_{DFA}, E_{CFG};
Unrecognizability of
A_{TM}
and E_{TM}

31  Nov 20  Chapter 4; 5.1 up to p192; 5.3  —  Time complexity, P and NP

32  Nov 21 (Xhr)  7.1 – 7.3  — 
NPcompleteness and polynomial time reductions
(slides)

33  Nov 27  7.4 up to p276; 7.5  HW7 
More NPcompleteness proofs 
34  Nov 28 (Xhr)  7.5  — 
Computation tableaux; The CookLevin theorem;
Unrecognizability of ALL_{CFG};

33  Nov 29  7.4  HW8 (optional)  Wrap up 
Dec 5  Takehome 48hour final exam, due at 6:00pm sharp 
If you are a registered student, you may verify your grades as entered in our database using the form below.