Course Homepage

Announcement!

Newsflash! Christmas comes early! (well, so does Hanukkah this year ...).
Check out the great new hints pages for lab 3!
(special thanks to Eric Chase for motivating discussions in lab!)

Note: Lecture notes and other materials make use of the Windows encoding of the TrueType Symbol font; without this font installed, or from a MacOS system, various Greek letters and math symbols will not appear correctly.

All lecture notes were produced using the HtX system, a compiler mapping LaTEX-like source to HTML target. Design and layout are based on the book jacket by Diane Levy for Michael Sipser's Introduction to the Theory of Computation


On-line lecture notes

  • Course introduction

    This lecture provides an informal introduction and some motivations for the basic ideas behind this course.

  • Review of relevant mathematics

    This lecture covers material from discrete math and foundations of mathematics that you should know as background for the course. It is also reviewed in greater depth in the text.

  • A graphic overview of computability issues

    These are some miscellaneous figures I've drawn for use in lecture; they're provided here for your perusal and exam review.


On-line programming projects

  • Lab #1: Simulating a DFA

    This is the first in a series of labs in which your group will implement a machine, grammar or other language-related construction as an interactive simulation. The main goal of these labs is to give provide you with a context in which you can express and test your understanding of the theoretical material presented in lectures and the textbook. In this particular lab you will implement a simple DFA (deterministic finite automaton).

    Assigned: Mon 16 Sep 2002
    Due: Mon 30 Sep 2002

  • Lab #2: Simulating an NFA

    This is the second in a series of labs in which your group will implement a class of machine as an interactive simulation. In this particular lab you will implement a simple NFA (nondeterministic finite automaton); the basic implementation choices involve direct simulation (e.g., using a queue to keep track of nondeterministic choices) or conversion to a DFA (followed by simulation as in the previous lab).

    Assigned: Wed 2 Oct 2002
    Due: Fri 18 Oct 2002

  • Lab #3: Converting Finite Machines to Regular Expressions

    For this project you will write a program which "reads in" an NFA as input and then converts it into an equivalent regular expression. (For the "reading in" part, you may use your interface for Lab #3.) The natural technique here is to use the "GNFA/state-ripping" algorithm which you have studied in the textbook and discussed in lecture. You may also wish to reduce the size of your regular expression output in order to make it easier to read (and to recognize as correct); this can be done by applying the rules for simplification given in the text (although others than those mentioned there might also be useful).

    Assigned: Wed 30 Oct 2002
    Due: Wed 20 Nov 2002

  • Lab #4: Simulation of Turing Machines

    For this project you will write a program which simulates a Turing machine. In some sense, therefore, you are implementing a universal Turing machine, but doing it in the (much more pleasant!) context of a high-level language.

    Assigned: not yet
    Due: after it's assigned


Written homework assignments