 Introduction to Automata
Theory, Languages, and Computation

Free Course in Automata Theory
I have prepared a course in automata theory (finite automata, contextfree grammars, decidability, and intractability), and
it begins April 23, 2012. You can learn more about the course at www.coursera.org/course/automata.
Several other courses will start at the same time, including Alex Aiken on Compilers, Mike Genesereth's Logic course,
Nick Parlante on computing for everyman/woman, and a repeat of ANdrew Ng's MachineLearning class.
You can learn about each of these courses at www.coursera.org/
Gradiance News
The Gradiance contract with Pearson (AddisonWesley + PrenticeHall) has terminated, and
we have decided to turn Gradiance into a FREE service.
If you are an instructor who wants to use the system, start
by creating an account for yourself at www.gradiance.com/services
NOT at the Pearson site.
Note: passwords are >= 10 letters+digits,
with at least one of each. Also, we cannot make an account be an
instructor account for a book if the same account has registered
as a student for a course using the same materials.
Then, email your chosen login,
with the book whose materials you want, to support@gradiance.com
We'll enable you to create a class using those materials.
There are manuals at www.gradiance.com/info.html
that should enable
you to use the system without problems, but feel free to email
support@gradiance.com if you encounter difficulties.
In addition, we have created eleven free "omnibus classes" covering Databases,
Automata, Compilers, Operating Systems, Introductory Java, Data Structures,
and Data Mining. Students wishing to join either one of these classes
will find the Student Directions useful.
NEW:
Jeff's Course Materials from Spring 2010 CS154.
Index
Table of Contents
The Table of Contents for the new book.
Solutions to Starred Exercises
Here are the
Solutions
to starred
exercises.
Errata
Our list is growing!
Send us a correction to ullman @ cs.stanford.edu
and see yourself acknowledged on the errata sheet.
Slides and Lecture Notes
The materials below are
available for use by others.
Instructors are welcome to use them in their own
courses, download them to their own class' web
site, or modify them to suit.
However, you must acknowledge the source of the original and not
attempt to place your own copyright on this material.
 Jeff's Lecture Notes for CS154,
Winter, 2000.
 Jeff's Slides for CS154, Spring 2010.
 Slides by Gosta
Grahne at Concordia University, Winter, 2002.
 Material
from Pierre Flener including the Grahne slides above, and other
materials in English and in Italian.
Course Materials
 Winter 2000 CS154 (Taught by
Jeff).
 Spring 2000
CS154 (Taught by Rajeev).
 Spring 2010 CS154 (Taught by Jeff).
Ordering Information