iv PREFACE

along with the mathematics. Thus, we have replaced a number of the more abstruse topics in the earlier book with examples of how the ideas are used today. While apphcations of automata and language theory to compilers are now so well understood that they are normally covered in a compiler course, there are a variety of more recent uses, including model-checking algorithms to verify protocols and document-description languages that are patterned on context-free grammars.

A final explanation for the simultaneous growth and shrinkage of the book is that we were today able to take advantage of the TfeK and ЖЩХ typesetting systems developed by Don Knuth and Les Lamport. The latter, especially, encourages the open style of typesetting that makes books larger, but easier to read. We appreciate the efforts of both men.

Use of the Book

This book is suitable for a quarter or semester course at the Junior level or above. At Stanford, we have used the notes in CS154, the course in automata and language theory. It is a one-quarter course, which both Rajeev and Jeff have taught. Because of the limited time available. Chapter 11 is not covered, and some of the later material, such as the more difficult polynomial-time reductions in Section 10.4 are omitted as well. The books Web site (see below) uacludes notes and syllabi for several offermgs of CS154.

Some years ago, we found that many graduate students came to Stanford with a course in automata theory that did not include the theory of intractability. As the Stanford faculty believes that these ideas are essential for every computer scientist to know at more than the level of NP-complete means it takes too long, there is another course, CS154N, that students may take to cover only Chapters 8, 9, and 10. They actually participate in roughly the last third of CS154 to fulfill the CS154N requhement. Even today, we find several students each quarter availing themselves of this option. Since it requires little extra effort, we recommend the approach.

Prerequisites

To make best use of this book, students should have taken previously a course covering discrete mathematics, e.g., graphs, trees, logic, and proof techniques. We assume also that they have had several courses in programming, and are familiar with common data structures, recursion, and the role of major system components such as compilers. These prerequisites should be obtained in a typical freshman-sophomore CS program.

Exercises

The book contains extensive exercises, with some for almost every section. We indicate harder exercises or parts o£ exercises with an exclamation point. The hardest exercises have a double exclamation point.

Some of the exercises or parts are marked with a star. For these exercises, we shall endeavor to maintain solutions accessible through the books Web page. These solutions are publicly available and should be used for self-testing. Note that in a few cases, one exercise В eisks for modification or adaptation of your solution to another exercise A. If certain parts of A have solutions, then you should expect the corresponding parts of В to have solutions as well.

Support on the World Wide Web

The books home page is

http: www-db.Stanford.edu/ ullman/ialc.html

Here are solutions to starred exercises, errata as we learn of them, and backup materials. We hope to make available the notes for each offering of CS154 as we teach it, including homeworks, solutions, and exams.

Acknowledgements

A handout on how to do proofs by Craig Silverstein influenced some of the material in Chapter 1. Comments and errata on drafts of this book were received from: Zoe Abrams, George Candea, Haowen Chen, Byong-Gun Chun, Jeffrey Shallit, Bret Taylor, Jason Townsend, and Erik Uzureau. They are gratefully acknowledged. Remainmg errors are ours, of course.

J. E. H. R. M. J. D. U.

Ithaca NY and Stanford CA September, 2000

Table of Contents

Automata: The Methods and the Madness 1

1.1 Why Study Automata Theory?................... 2

1.1.1 Introduction to Finite Automata.............. 2

1.1.2 Structural Representations ................. 4

1.1.3 Automata and Complexity ................. 5

1.2 Introduction to Formal Proof.................... 5

1.2.1 Deductive Proofs....................... 6

1.2.2 Reduction to Definitions................... 8

1.2.3 Other Theorem Forms.................... 10

1.2.4 Theorems That Appear Not to Be If-Then Statements . , 13

1.3 Additional Forms of Proof...................... 13

1.3.1 Proving Ekjuivalences About Sets.............. 14

1.3.2 The Contrapositive...................... 14

1.3.3 Proof by Contradiction................... 16

1.3-4 Counterexamples....................... 17

1.4 Inductive Proofs........................... 19

1.4.1 Inductions on Integers.................... 19

1.4.2 More General Forms of Integer Inductions......... 22

1.4.3 Structural Inductions .................... 23

1.4.4 Mutual Inductions...................... 26

1.5 The Central Concepts of Automata Theory............ 28

1.5.1 Alphabets........................... 28

1.5.2 Strings............................. 29

1.5.3 Languages........................... 30

1.5.4 Problems........................... 31

1.6 Summary of Chapter 1........................ 34

1.7 References for Chapter 1....................... 35

Finite Automata 37

2.1 An Informal Picture of Finite Automata.............. 38

2.1.1 The Ground Rules...................... 38

2.1.2 The Protocol......................... 39

2.1.3 Enabling the Automata to Ignore Actions......... 41