Introduction To Automata Theory, Languages, And Computation 3rd.pdf-资料库

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第1页.png

第1页 / 共550页

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第2页.png

第2页 / 共550页

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第3页.png

第3页 / 共550页

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第4页.png

第4页 / 共550页

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第5页.png

第5页 / 共550页

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第6页.png

第6页 / 共550页

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第7页.png

第7页 / 共550页

33b8ea9a-fb72-4d0b-94ac-6022fc38449b.pdf-第8页.png

第8页 / 共550页

hopcroft_titlepgs 5/8/06 12:43 PM Page 1 I N T R O D U C T I O N T O Automata Theory, Languages, and Computation 3rd Edition

hopcroft_titlepgs 5/8/06 12:43 PM Page 2 I N T R O D U C T I O N T O Automata Theory, Languages, and Computation 3rd Edition J O H N E . H O P C R O F T Cornell University R A J E E V M O T W A N I Stanford University J E F F R E Y D . U L L M A N Stanford University

Joe Vetere Greg Tobin Michael Hirsch Matt Goldstein Katherine Harutunian Jeffrey Holcomb Joyce Cosentino Wells Marianne Groth Bethany Tidd Michelle Brown Dana Lopreato Publisher Executive Editor Acquisitions Editor Project Editor Associate Managing Editor Cover Designer Digital Assets Manager Media Producer Marketing Manager Marketing Assistant Senior Author Support/ Technology Specialist 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 Congress Cataloging-in-Publication Data 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 predecessor to this book Hopcroft and Ullman marveled at the fact that the subject of automata had exploded compared with its state at the time they wrote their rst book in Truly the book contained many topics not found in the earlier work and was about twice its size If you compare this book with the book you will nd that like the automobiles of the s this book 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 automata and language theory was still an area of active research A purpose 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 opposed to its applications and thus little motivation for us to retain the succinct highly mathematical tone of the book Second the role of automata and language theory has changed over the past two decades In automata was largely a graduatelevel subject and we imagined our reader was an advanced graduate student especially those using the later chapters of the book Today the subject is a staple of the undergraduate curriculum As such the content of the book must 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 book A third change in the environment is that Computer Science has grown to an almost unimaginable degree in the past three decades While in it was often a challenge to ll up a curriculum with material that we felt would survive the next wave of technology today very many subdisciplines compete for the limited amount of space in the undergraduate curriculum Fourthly CS has become a more vocational subject and there is a severe pragmatism among many of its students We continue to believe that aspects of automata theory are essential tools in a variety of new disciplines and we believe that the theoretical mindexpanding exercises embodied in the typical automata course retain their value no matter how much the student prefers to learn only the most immediately monetizable technology However to assure a continued place for the subject 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 understood that they are normally covered in a compiler course there are a variety of more recent uses including modelchecking algorithms to verify protocols and documentdescription languages that are patterned on contextfree grammars A nal explanation for the simultaneous growth and shrinkage of the book is that we were today able to take advantage of the TEX and LATEX 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 eorts 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 CS the course in automata and language theory It is a onequarter course which both Rajeev and Je have taught Because of the limited time available Chapter is not covered and some of the later material such as the more dicult polynomialtime reductions in Section are omitted as well The books Web site see below includes notes and syllabi for several oerings of CS 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 intractabil ity As the Stanford faculty believes that these ideas are essential for every computer scientist to know at more than the level of NPcomplete means it takes too long there is another course CSN that students may take to cover only Chapters and They actually participate in roughly the last third of CS to fulll the CSN requirement Even today we nd several students each quarter availing themselves of this option Since it requires little extra eort we recommend the approach Prerequisites To make best use of this book students should have taken previously a course covering discrete mathematics eg 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 freshmansophomore CS program

PREFACE Exercises vii The book contains extensive exercises with some for almost every section We indicate harder exercises or parts of 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 selftesting Note that in a few cases one exercise B asks for modication or adaptation of your solution to another exercise A If certain parts of A have solutions then you should expect the corresponding parts of B to have solutions as well Gradiance OnLine Homeworks A new feature of the third edition is that there is an accompanying set of online homeworks using a technology developed by Gradiance Corp Instructors may assign these homeworks to their class or students not enrolled in a class may enroll in an omnibus class that allows them to do the homeworks as a tutorial without an instructorcreated class Gradiance questions look like ordinary questions but your solutions are sampled If you make an incorrect choice you are given specic advice or feedback to help you correct your solution If your instructor permits you are allowed to try again until you get a perfect score A subscription to the Gradiance service is oered with all new copies of this text sold in North America For more information visit the AddisonWesley web site wwwawcomgradiance or send email to computingawcom Support on the World Wide Web The books home page is httpwwwdbstanfordeduullmanialchtml Here are solutions to starred exercises errata as we learn of them and backup materials We hope to make available the notes for each oering of CS as we teach it including homeworks solutions and exams Acknowledgements A handout on how to do proofs by Craig Silverstein inuenced some of the material in Chapter Comments and errata on drafts of the second edition were received from Zoe Abrams George Candea Haowen Chen Byong Gun Chun Jerey Shallit Bret Taylor Jason Townsend and Erik Uzureau We also received many emails pointing out errata in the second edition of this book and these were acknowledged online in the errata sheets for that

viii PREFACE edition However we would like to mention here the following people who provided large numbers of signicant errata Zeki Bayram Sebastian Hick KangRae Lee Christian Lemburg Nezam MahdaviAmiri Dave Maier A P Marathe Mark Meuleman Mustafa SaitAmetov Alexey Sarytchev Jukka Suomela Rod Topor PoLian Tsai Tom Whaley Aaron Windsor and Jacinth HT Wu The help of all these people is greatefully acknowledged Remaining errors are ours of course J E H R M J D U Ithaca NY and Stanford CA February

Table of Contents Automata The Methods and the Madness Introduction to Formal Proof Why Study Automata Theory Introduction to Finite Automata Structural Representations Automata and Complexity Deductive Proofs Reduction to Denitions Other Theorem Forms Theorems That Appear Not to Be IfThen Statements Additional Forms of Proof Proving Equivalences About Sets The Contrapositive Proof by Contradiction Counterexamples Inductions on Integers More General Forms of Integer Inductions Mutual Inductions The Central Concepts of Automata Theory Alphabets Strings Languages Problems Summary of Chapter Gradiance Problems for Chapter References for Chapter Inductive Proofs Structural Inductions Finite Automata An Informal Picture of Finite Automata The Ground Rules The Protocol ix

资料库

Introduction To Automata Theory, Languages, And Computation 3rd.pdf

相关推荐

课程资源

热门标签

最新资料