Course Overview

Language processing is an important task in computer science (c.f., compilers and interpreters) and its applications (c.f., biological sequence analysis). It is a hugely important point of contact between theoretical and applied computer science. This is a "theorem/proof" course, and this is the skill you'll be expected to master, and will be assessed on.


The instructor is Professor Stuart A. Kurtz.

Generally speaking, the best way to communicate with me outside of class is via email, at stuart@cs.uchicago.edu. If you do send me email, please include include the string "[28000]" in the subject line, e.g.,

Subject: [28000] Homework questions...

Professor Kurtz's office hours are 2:00–3:00 MWF, and by appointment. Please feel free to ask to set up an appointment if my regular hours don't work for you, and I will try to accommodate you as quickly as possible. My office is Ryerson 166.

Support Staff

The teaching assistants are

NameOffice Hoursuchicago emailLocation
Jafar JararovMon, Thurs 4:30-6:00 pmjafarovE 129
Jingwen JiangWed, Fri 5:00-6:30pmjingwenE 129
Areej KhouryMon, Weds 1:00pm-2:30pmareejkhouryRy 162
Aritra SenTue, Wed 3:30-4:30 pm
Fri 3:00-4:00pm
aritrasenRy 162


The required textbook is Automata and Computability by Dexter Kozen.


Grading will be based on homework (1/2), the midterm (1/6) and the final exam (1/3). Unless otherwise noted, homework assigned during one lecture will be due at the beginning of the following lecture.

Only the starred (*) exercises from the Lecture notes will be assessed. This doesn't mean that the others are unimportant! Do them all.

How to succeed in this course (and in College)

You should work hard. But hard work is not enough to guarantee success. You need to work hard, and smart.

  1. Ask questions. Ask questions during lectures, in study group meetings, at office hours. Don't assume, if you don't understand something now, you'll figure it out later by yourself and all will be well. Ideas build on ideas, and not understanding something now can undermine your foundation, leaving you behind and struggling.
  2. Do all of the assessed work. The difference between A students and everyone else has less to do with the A students jumping better, and more to do with their reliability in jumping when and how they're expected to.
  3. Form study groups. Meet 2-3 times a week for an hour or so. Review the lectures, the homework (both pending and graded). Make sure you understand what you've been taught, what you have to do, and the feedback you're getting.
  4. Take advantage of the office hours for the course instructors and TAs. If you can't make your instructor's posted hours, ask to meet at a time that works for you. Consider meeting with the TAs, who might have a different “take” on something that has you stumped. Please understand that we like to have students come to our office hours. It is perfectly reasonable, if your group can't figure something out, for the whole group to come to office hours.