Computer Science Dartmouth College 
Computer Science 39 
Fall 2005 
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: MF 10:0011:30 or by appointment 
Teaching Assistant 
Khanh Do Ba  Sudikoff 114  65573  Office hours: Tu 17:0019:00, Th 19:0021: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.
L# 
Date 
Reading Due 
Homework Due 
Class Topic 
1  Sep 21  —  —  Welcome, administrivia, overview; Mathematical notation (slides) 
2  Sep 23  0.1, 0.2, 0.3  —  Types of proof: by construction, by contradiction, by induction (slides) 
3  Sep 26  0.4  —  Strings and languages; Finite automata introduced (slides) 
4  Sep 27 (Xhr)  1.1 up to p34  — 
More on (deterministic) finite automata; examples of DFAs;
formal definition as (Q,Σ,δ,q_{0},F) 
5  Sep 28  1.1  — 
Formal definition of a DFA recap; how to design a DFA, examples

6  Sep 30  —  — 
DFA computation formalized; NFA introduced, examples 
7  Oct 3  —  — 
Designing NFAs; Union and concatenation of two regular languages
is regular 
8  Oct 4 (Xhr)  —  — 
Kleene star; Regular expressions and examples 
9  Oct 5  1.3 up to p66  HW1 
Equivalence of DFAs, NFAs and regular expressions, I 
10  Oct 7  1.2  — 
Equivalence of DFAs, NFAs and regular expressions, II 
11  Oct 10  1.3  — 
Equivalence of DFAs, NFAs and regular expressions, III
(lecture notes) 
12  Oct 11 (Xhr)  —  — 
Example of DFA to RegExp conversion; The pumping lemma 
13  Oct 12  —  HW2 
Proof and applications of the pumping lemma 
14  Oct 14  1.4  — 
Closure properties of regular languages 
15  Oct 17  Chapter 1  — 
Wrapup of regular language theory; pushdown automata 
Oct 18 (Xhr)  —  — 
Quiz 1: closednotes, inclass 

16  Oct 19  —  HW3 
Discussion of Quiz 1; more examples of pushdown automata (PDAs)

Oct 21  No lecture; homecoming  
17  Oct 24  2.2  — 
Closure properties of PDAs (union, concatenation)

18  Oct 25 (Xhr)  —  — 
Closure and nonclosure properties;
PDA for notww 
19  Oct 26  —  HW4 
Contextfree grammars; Simple examples 
20  Oct 28  —  — 
More CFG examples; equally many 0s and 1s

21  Oct 31  2.1  — 
Equivalence of CFGs and PDAs, I (PDA to CFG) 
22  Nov 1 (Xhr)  —  — 
Equivalence of CFGs and PDAs, II (CFG to PDA)

23  Nov 2  2.2 (again)  Midterm 
Pumping lemma for contextfree languages; Applications

24  Nov 4  2.3  — 
Chomsky Normal Form; Proof of the pumping lemma for CFLs 
25  Nov 7  Chapter 2  — 
Turing machines; Informal description and simple examples 
26  Nov 8 (Xhr)  3.1 up to p133  — 
Two TM applets; TM formalized; Configurations

27  Nov 9  —  HW5 
Deciders/recognizers; Multitape TMs; Closure properties of
decidable languages
(slides) 
28  Nov 11  —  — 
Nondeterministic TMs; the RAM model; ChurchTuring Thesis
(slides) 
29  Nov 14  Chapter 3  — 
Enumerator TMs; Decision problems for the major language classes:
A_{DFA}, A_{CFG} and A_{TM} 
Nov 15 (Xhr)  —  — 
Quiz 2: closednotes, inclass 

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

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

32  Nov 21  Chapter 4  —  Time complexity, P and NP

33  Nov 22 (Xhr)  5.1 up to p192; 5.3  — 
NPcompleteness and polynomial time reductions
(slides)

34  Nov 28  7.1  7.3  HW7 
More NPcompleteness proofs 
35  Nov 29 (Xhr)  7.5  — 
Computation tableaux; The CookLevin theorem;
Unrecognizability of ALL_{CFG};

36  Nov 30  7.4  HW8 (optional)  Wrap up 
Dec 6  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.