2009 June 8 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Automata And Computability

Carleton College CS 254, Fall 2008, Prof. Joshua R. Davis


This course is about theoretical models of computation. We investigate three main models: finite automata, push-down automata, and Turing machines. Along the way we witness a few monumental intellectual achievements of the 20th century.

This course is required for the CS major here at Carleton. Many CS programs require such a course. To students who are primarily interested in programming it is not always clear why. I think the reason can be summarized in one word: perspective. Theory helps us see patterns among the lower-level material that we encounter, as well as patterns among those patterns. It lets us see past the "flavor of the week" programming language to the larger trend of the computer industry. It explains why some systems and languages are designed as they are. The general sentiment among computer scientists is that learning this theory truly helps you become a better programmer. For example, after taking this course you should be able to guess quickly whether a programming task is solvable using regular expressions, and solve it if it is.

The official prerequisites for this course are CS 201 (Data Structures) and CS 202 (Mathematics Of Computer Science). Math 236 may be substituted for CS 202. The course is more dependent on CS 202 than on CS 201, because we write more proofs than programs, but some programming is expected. Talk to me if you are concerned about your background.

Our class meets in CMC 328 during period 2A (MW 9:50AM-11:00AM, F 9:40AM-10:40AM). The course materials are

Here's how you get in contact with me:

Dr. Joshua R. Davis (most people call me Josh)
E-mail: |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Office: CMC 327, x4482
Office hours: Mon 3:00-3:50, Tue 2:00-2:50, Wed 3:00-3:50, Thu 1:00-1:50. You can also make an appointment; simply pick a free time from my weekly schedule and e-mail me. You can also talk to me after class.


Final grades (A, B, C, etc.) are assigned according to an approximate curving process. By this I mean that there are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades. The following elements contribute to the final grade.

You are expected to spend at least 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you find yourself spending more than, say, 15 hours, then talk to me.

Working With Others

You are strongly encouraged to work with others on all assignments. Work together to figure out the problems/programs, but write/type them up separately, in your own words. You may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is an act of Academic Dishonesty.

Written Work

Writing is not just for English majors. Written and oral communication skills are essential to every academic discipline; they are also highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation. You may find it easier to type your solutions in LaTeX than to edit them by hand.

How much work should you show? The answer is simple: Compose your solutions as if the intended audience is your fellow students. By doing so, you show enough detail that your grader can ascertain whether you yourself understand the material. Your solutions should also be self-explanatory. In short, if a classmate were to read one of your solutions, then she or he should be able to understand what the problem was and how you solved it.

Staple your solutions into a single packet, in the order they were assigned. Packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Staple your packet. Your packet? Staple it.

Depending on time constraints in any given week, perhaps not all of your homework is graded; in order to ensure full credit, do all of the assigned problems.

Special Accommodations

During the term, you have one free pass to hand in an assignment late. Here is how you activate it. Instead of handing in the assignment, send me e-mail (by the due date) declaring that you are using your late pass and proposing a new due date. If the due date is extended by only one class meeting, then no explanation is necessary; if you need longer, then convince me. Use your free pass wisely; once you have used it, no late assignments are accepted, except in extreme circumstances that are truly beyond your control.

If some medical condition affects your participation in class or your taking of exams, let me know in the first week of class. You may need to make official arrangements with the Office of Disability Services.


M 3/300101, 02introductionIntroduction
W 4/010203deterministic finite automatadfas.py
F 4/030304regular languagesAssignment 2
M 4/060405, 06nondeterministic finite automata
W 4/080507, 08regular expressions
F 4/100609REsAssignment 3
M 4/130711, 12pumping lemmaAssignment 4Python REs
W 4/150813, 14minimizing DFAs
F 4/170915, 16Myhill-Nerode
M 4/2010catch-up, review
W 4/221119, 20context-free grammars
F 4/2412Exam 1
M 4/271321, 22normal forms, pumping lemma
W 4/291423push-down automataAssignment 5
F 5/011524PDAs from CFGs
M 5/04Midterm Break
W 5/061625CFGs from PDAs
F 5/0817catch up
M 5/111826, 28parsing, Turing machinesAssignment 6
W 5/131929, 30TMs
F 5/152031universal TMsExam 2
M 5/182132undecidable problems
W 5/202233reduction
F 5/222334Rice's theoremAssignment 7
M 5/252436unrestricted grammars
W 5/272537combinatorial logic
F 5/2926information theoryAssignment 8Notes
M 6/0127information theory
W 6/0328information theory
S 6/07Final Exam 3:30PM-6:00PM