INTRODUCTION TO
Automata Theory,
Languages,
and
Computation
3rd Edition
hopcroft_titlepgs 5/8/06 12:43 PM Page 1
INTRODUCTION TO
Automata Theory,
Languages,
and
Computation
JOHN E. HOPCROFT
Cornell University
RAJEEV MOTWANI
Stanford University
JEFFREY D. ULLMAN
Stanford University
3rd Edition
hopcroft_titlepgs 5/8/06 12:43 PM Page 2
Publisher Greg Tobin
Executive Editor Michael Hirsch
Acquisitions Editor Matt Goldstein
Project Editor Katherine Harutunian
Associate Managing Editor Jeffrey Holcomb
Cover Designer Joyce Cosentino Wells
Digital Assets Manager Marianne Groth
Media Producer Bethany Tidd
Marketing Manager Michelle Brown
Marketing Assistant Dana Lopreato
Senior Author Support/
Technology Specialist Joe Vetere
Senior Manufacturing Buyer Carol Melville
Media Manufacturing Buyer Ginny Michaud
Many of the exercises that appear in this text use the stems of questions from
Gradiance Corporation, which retains the copyright to all such questions.
© Gradiance Corp., 2004–2006
Many of the designations used by manufacturers and sellers to distinguish their
products are claimed as trademarks. Where those designations appear in this book,
and Addison-Wesley was aware of a trademark claim, the designations have been
printed in initial caps or all caps.
Library of Con gress Ca tal oging-in-Pu blication Da t a
Hopcroft, John E., 1939-
Introduction to automata theory, languages, and computation / by John E. Hopcroft,
Rajeev Motwani, Jeffrey D. Ullman. -- 3rd ed.
p. cm.
Includes bibliographical references and index.
ISBN 0-321-45536-3
1. Machine theory. 2. Formal languages. 3. Computational complexity. I.
Motwani, Rajeev. II. Ullman, Jeffrey D., 1942- III. Title.
QA267.H56 2006
511.3'5--dc22
2006014263
Copyright © 2007 Pearson Education, Inc. All rights reserved. No part of this
publication may be reproduced, stored in a retrieval system, or transmitted, in any
form or by any means, electronic, mechanical, photocopying, recording, or
otherwise, without the prior written permission of the publisher. Printed in the
United States of America. For information on obtaining permission for use of
material in this work, please submit a written request to Pearson Education, Inc.,
Rights and Contracts Department, 75 Arlington Street, Suite 300, Boston, MA
02116, fax your request to 617-848-7047, or e-mail at
http://www.pearsoned.com/legal/permissions.htm.
1 2 3 4 5 6 7 8 9 10—CW—10 09 08 07 06
Preface
In the preface from the 1979 predecessor to this book, Hop croft and Ullman
marveled at the fact that the sub ject of automata had explo ded, compared with
its state at the time they wrote their rst b o ok, in 1969. Truly, the 1979 bo ok
contained many topics not found in the earlier work and was ab out twice its
size. If you compare this bo ok with the 1979 bo ok, you will nd that, likethe
automobiles of the 1970's, this bo ok is \larger on the outside, but smaller on
the inside." That sounds like a retrograde step, but we are happy with the
changes for several reasons.
First, in 1979, automata and language theory was still an area of active
research. A purp ose of that book was to encourage mathematically inclined
students to make new contributions to the eld. Today, there is little direct
research in automata theory (as opp osed to its applications), and thus little
motivation for us to retain the succinct, highly mathematical tone of the 1979
book.
Second, the role of automata and language theory has changed over the
past two decades. In 1979, automata was largely a graduate-level sub ject, and
we imagined our reader was an advanced graduate student, esp ecially those
using the later chapters of the bo ok. Today, the sub ject is a staple of the
undergraduate curriculum. As such, the contentofthebookmust assume less
in the way of prerequisites from the student, and therefore must provide more
of the background and details of arguments than did the earlier bo ok.
A third change in the environment is that Computer Science has grown to
an almost unimaginable degree in the past three decades. While in 1979 it was
often a challenge to ll up a curriculum with material that we felt would survive
the next waveoftechnology, to dayvery many sub disciplines comp ete for the
limited amount of space in the undergraduate curriculum.
Fourthly, CS has become a more vocational sub ject, and there is asevere
pragmatism among many of its students. Wecontinue to believe that asp ects
of automata theory are essential tools in a varietyofnew disciplines, and we
believe that the theoretical, mind-expanding exercises embodied in the typical
automata course retain their value, no matter howmuch the student prefers to
learn only the most immediately monetizable technology. However, to assure
acontinued place for the sub ject on the menu of topics available to the com-
puter science student, we believe it is necessary to emphasize the applications
v
vi
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 applications of automata and language theory to compilers are
now so well understo o d that they are normally covered in a compiler course,
there are a variety of more recent uses, including mo del-checking algorithms
to verify proto cols and document-description languages that are patterned on
context-free grammars.
A nal explanation for the simultaneous growth and shrinkageofthebook
is that wewere to day able to take advantage of the T
E
X and L
A
T
E
Xtyp esetting
systems dev
eloped by Don Knuth and Les Lamp ort. The latter, esp ecially,
encourages the \op en" style of typ esetting that makes b o oks larger, but easier
to read. We appreciate the eorts of both men.
Use of the Bo ok
This book is suitable for a quarter or semester course at the Junior level or
above. At Stanford, wehave used the notes in CS154, the course in automata
and language theory. It is a one-quarter course, which b oth Ra jeev and Je have
taught. Because of the limited time available, Chapter 11 is not covered, and
some of the later material, such as the more dicult p olynomial-time reductions
in Section 10.4 are omitted as well. The b ook's Web site (see below) includes
notes and syllabi for several oerings of CS154.
Some years ago, wefound that many graduate students came to Stanford
with a course in automata theory that did not include the theory of intractabil-
ity. As the Stanford faculty b elieves 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 fulll the CS154N requirement. Even to day,wendseveral
students each quarter availing themselves of this option. Since it requires little
extra eort, we recommend the approach.
Prerequisites
Tomake best use of this b ook, students should have taken previously a course
covering discrete mathematics, e.g., graphs, trees, logic, and pro of techniques.
We assume also that they have had several courses in programming, and are
familiar with common data structures, recursion, and the role of ma jor system
components such as compilers. These prerequisites should be obtained in a
typical freshman-sophomore CS program.
