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

Introduction

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.

• Alan Turing proved around 1936 that there are some seemingly computational tasks that computers simply cannot solve. In other words, there is a fundamental limit on the complexity of problems solvable by computers.
• Turing also proved that his notion of computation was essentially equivalent to earlier notions such as Alonzo Church's λ-calculus. The λ-calculus is the basis for the LISP programming language, which has influenced many other languages. When you program a computer in one of these languages, you are living Turing's theorem.
• Kurt Gödel proved in 1931 that (in any reasonable version of mathematics) there are some true statements that cannot be proven to be true. There is a close parallel here between computation and logic. In fact, Turing based his work on Gödel's.
• Noam Chomsky in 1956 invented a hierarchy of four kinds of grammar for describing the syntax of natural languages such as English. It turns out that these grammars exactly correspond to finite automata, push-down automata, linear bounded automata (which we will not study), and Turing machines. There is an intimate connection here between computation and syntax.

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

• Automata and Computability by Dexter C. Kozen. This text has been used in recent terms at Carleton. Kozen also has a graduate-level computability textbook; don't get that one.
• Exam 1 (Percentiles: 75th = 31/40, 50th = 28/40, 25th = 23/40)
• Exam 2, Answers (Percentiles: 75th = 28/32, 50th = 25.5/32, 25th = 23/32)
• Exam 3 (Percentiles: 75th = 25/32, 50th = 20/32, 25th = 17/32)

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.

Responsibilities

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.

• Participation: This is a measure of how engaged with the course you are. You are expected to attend every class meeting (promptly) and participate in the discussion and group work. You are expected to have read the relevant textbook sections before class; you will then get much more out of the discussion! You are also required to visit me in my office at least once during the first two weeks. You can make up for a deficiency in class participation by talking with me frequently in office hours or generally demonstrating exceptional effort and interest. Participation is used to make small adjustments to the class grades.
• Assignments: In this course, most of your learning takes place while doing homework assignments. Most assignments take the form of problem sets, but there are occasional programs too. To give you some flexibility, assignments are collected on Wednesdays rather than at every meeting. They count for 25% of your grade.
• Exam 1: The first midterm exam is given in class about 1/3 of the way through the term. It counts for 25% of your grade.
• Exam 2: The second midterm exam is cumulative and given as a take-home exam about 2/3 of the way through the term. It counts for 25% of your grade.
• Final Exam: The final exam is cumulative. It is scheduled for Sunday 2009 June 7, 3:30PM-6:00PM. Self-scheduled final exams are not allowed. It counts for 25% of your 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.

Schedule

Date	Day	Reading	Topic	Assignment	Notes
M 3/30	01	01, 02	introduction	Introduction
W 4/01	02	03	deterministic finite automata		dfas.py
F 4/03	03	04	regular languages	Assignment 2
M 4/06	04	05, 06	nondeterministic finite automata
W 4/08	05	07, 08	regular expressions
F 4/10	06	09	REs	Assignment 3
M 4/13	07	11, 12	pumping lemma	Assignment 4	Python REs
W 4/15	08	13, 14	minimizing DFAs
F 4/17	09	15, 16	Myhill-Nerode
M 4/20	10		catch-up, review
W 4/22	11	19, 20	context-free grammars
F 4/24	12	Exam 1
M 4/27	13	21, 22	normal forms, pumping lemma
W 4/29	14	23	push-down automata	Assignment 5
F 5/01	15	24	PDAs from CFGs
M 5/04	Midterm Break
W 5/06	16	25	CFGs from PDAs
F 5/08	17		catch up
M 5/11	18	26, 28	parsing, Turing machines	Assignment 6
W 5/13	19	29, 30	TMs
F 5/15	20	31	universal TMs	Exam 2
M 5/18	21	32	undecidable problems
W 5/20	22	33	reduction
F 5/22	23	34	Rice's theorem	Assignment 7
M 5/25	24	36	unrestricted grammars
W 5/27	25	37	combinatorial logic
F 5/29	26		information theory	Assignment 8	Notes
M 6/01	27		information theory
W 6/03	28		information theory
S 6/07	Final Exam 3:30PM-6:00PM