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