Introduction to Automata Theory, Languages, and Computation

Free Course in Automata Theory

I have prepared a course in automata theory (finite automata, context-free 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 Machine-Learning class. You can learn about each of these courses at www.coursera.org/

Gradiance News

The Gradiance contract with Pearson (Addison-Wesley + Prentice-Hall) 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.

  1. Jeff's Lecture Notes for CS154, Winter, 2000.
  2. Jeff's Slides for CS154, Spring 2010.
  3. Slides by Gosta Grahne at Concordia University, Winter, 2002.
  4. Material from Pierre Flener including the Grahne slides above, and other materials in English and in Italian.

Course Materials

  1. Winter 2000 CS154 (Taught by Jeff).
  2. Spring 2000 CS154 (Taught by Rajeev).
  3. Spring 2010 CS154 (Taught by Jeff).

Ordering Information