CS237 (Theory of Computation)
Spring 2007, Carleton College
Basic information:
- Instructor: David
Liben-Nowell
- Lecture: 2a (MW 9:50--11:00p, F 9:40--10:40a), CMC 210.
- Office Hours: see my homepage.
Always feel free to email for an appointment if the scheduled times
aren't good for you.
- Official catalogue description:
All about computing machines: abstract automata, especially finite
state machines, push-down automata, and Turing machines. Formal
languages, especially context-free languages. The relationship between
automata and languages. Computability and solvability. Prerequisites:
Computer Science 127; Computer Science 177 or Mathematics 236
or consent of the instructor.
Announcements:
- There is an anonymous feedback
form available for any comments that you have about the course.
If you have any suggestions or comments on the class (style, content,
workload, etc.), please feel free to use this form to let me
know.
- The Carleton Sentinel is the mailing list of the CS community here
at Carleton. We'll use it to send occasional updates on things that
might be of interest. Sign up here!
Course Materials:
Week 0:
There is a
form for
office-hours scheduling available. Please fill it out by Tuesday,
20 March 2007, and I'll schedule office hours soon thereafter. (Be
sure to include your email address!)
Week 1: course overview; DFAs
- 26 March 2007 (M): history of computing (600 BCE ff.), strings,
languages. Reading: L01, L02.
- 28 March 2007 (W): more on strings and sets, DFAs. Reading: L02,
L03.
- 30 March 2007 (F): more regular languages, closure of regular
languages under complement. Reading: L03, L04.
Week 2: NFAs, closure properties of the
regular languages, regular expressions
Problem Set #1 is due on Monday and Wednesday.
- 2 April 2007 (M): product construction, nondeterminism and NFAs.
Reading: L04, L05, L06.
- 4 April 2007 (W): subset construction. Reading: L05, L06.
- 6 April 2007 (F): patterns and regular expressions. Reading: L07,
L08, L09.
Week 3: non-regular languages
Problem Set #2 is due on Monday and Wednesday.
- 9 April 2007 (M): equivalence of regular expressions and DFAs.
Reading: L08, L09.
- 11 April 2007 (W): non-regular languages and the pumping lemma.
Reading: L11, L12.
- 13 April 2007 (F): DFA state minimization. Reading: L13,
L14.
Week 4: regular language miscellanea
Problem Set #3 is due on Monday and Wednesday.
Our first midterm is scheduled for Monday, 23
April 2007, in class. You may bring one 8.5"-by-11" crib
sheet containing notes that you have handwritten or typed yourself (no
photocopying). You may write on both sides of the paper, but don't
staple/tape/superglue/attach anything to the paper. You will be asked
to hand in your crib sheet with your exam. Any material related to
regular languages is fair game for the exam.
- 16 April 2007 (M): DFA state minimization, homomorphisms.
Reading: L14, L10, L12.
- 18 April 2007 (W): homomorphisms, ultimate periodicity,
Myhill–Nerode relations. Reading: L10, L12, L15–18.
- 20 April 2007 (F): context-free languages and grammars. Reading:
L19.
Week 5: context-free languages
Problem Set #4 is due on Wednesday.
- 23 April 2007 (M): midterm #1
- 25 April 2007 (W): balanced parentheses, normal forms. Reading:
L20, L21, L27.
- 27 April 2007 (F): CFL closure properties and the CKY algorithm.
Reading: L27.
Week 6: non-context-free languages, PDAs,
closure properties
Problem Set #5 is due on Wednesday.
- 30 April 2007 (M): midterm break!
- 2 May 2007 (W): pushdown automata. Reading: L23; skim LE, L24,
L25 (at least for the results).
- 4 May 2007 (F): non-context-free languages. Reading: L22, L27.
Week 7: CFL miscellanea, Turing machines
Problem Set #6 is due on Wednesday.
Our second midterm is Friday, 11 May 2007, in
class. You may bring one 8.5"-by-11" crib sheet containing
notes that you have handwritten or typed yourself (no photocopying).
You may write on both sides of the paper, but don't
staple/tape/superglue/attach anything to the paper. You will be asked
to hand in your crib sheet with your exam. Any material related to
context-free or regular languages is fair game for the exam.
- 7 May 2007 (M): class cancelled!
Find a nice tree and read L26 and the parsing handout under it.
- 9 May 2007 (W): CFL wrapup, intro to Turing machines. Reading:
L28, L29.
- 11 May 2007 (F): midterm #2
Week 8: Turing machines, computability
Problem Set #7 is due on Wednesday and Friday.
- 14 May 2007 (M): more on Turing machines. Reading: L29, L30.
- 16 May 2007 (W): some TM-like models. Reading:
L30, L31.
- 18 May 2007 (F): uncomputability and diagonalization. Reading:
L31, L32.
Week 9: decidability and undecidability
Problem Set #8 is due on Wednesday and Friday.
(Update: skip #5; only 2 questions are due Wednesday.)
- 21 May 2007 (M): the halting problem, more on undecidability.
Reading: L31, L32, L33.
- 23 May 2007 (W): reductions and more undecidable problems.
Reading: L33, L34.
- 25 May 2007 (F): Rice's Theorem. Reading: L34.
Week 10: undecidable problems, Gödel's Incompleteness Theorem
Problem Set #9 is due on Wednesday.
- 28 May 2007 (M): VALCOMPs and undecidable problems about CFLs.
Reading: L35.
- 30 May 2007 (W): Gödel's incompleteness theorem. Reading:
L38, L39, LK.
Finals Period:
Resources/clarifications for the final:
- If you'd like to use LaTeX to type your solutions, you should take
a look at this tutorial.
LaTeX is installed on the CS machines, and you can use it by typing
latex exam.tex (or whatever).
- If you want to use a completely obvious fact in your solutions,
you can assert that fact without proof. Use common sense regarding
what is or is not completely obvious.