1610906232-7ba7dbaea13262b50a6029d682cb7f1b (Elements of Theory of Computation 2ed Lewis Papadimitriou)

ELEMENTS OF THETHEORY OFCOMPUTATIONSecond EditionHarry R. LewisGordon McKay Professor of Computer ScienceHarvard Universityand Dean of Harvard CollegeCambridge, MassachusettsChristos H. PapadimitriouC. Lester Hogan Professor of Electrical Engineeringand Computer ScienceUniversity of CaliforniaBerkeley, CaliforniaPRENTICE-HALL, Upper Saddle River, New Jersey 07458Library of Congress Cataloging-in-PubJication DataLewis, Harry R.Elements of the theory of computation I Harry R. Lewis andChristos H.

Papadimitriou. - 2nd ed.p. em.Includes bibliological references and index.ISBN: 0-13-26247&-8I. Machine theory. 2. Formal languages. 3. Computationalcomplexity. 4. Logic, Symbolic and mathematical.I. Papadimitriou. Christos H.II. Title.QA267.L491998511.3--<1c2197-13879OPPublisher: Alan AptDevelopment Editor: Sondra ChavezEditorialJProduction Supervision: Barbara KraemerManaging Editor: Bayani Mendoza DeLeonEditor-in-Chief: Marcia HortonAssistant Vice President of Production and Manufacturing: David W. RiccardiArt Director: Jayne ConteManufacturing Manager: Trudy PisciottiManufacturing Buyer: Donna SullivanEditorial Assistant: Toni Holm©1998 by Prentice-Hall, Inc.Simon & Schuster I A Viacom CompanyUpper Saddle River, New Jersey 07458All rights reserved.

No part of this book may bereproduced, in any form or by any means,without permission in writing from the publisher.The author and publisher of this book have used their best efforts in preparing this book. These effortsinclude the development, research, and testing of the theories and programs to determine their effectiveness.The author and publisher make no warranty of any kind, expressed or implied, with regard to these programsor the documentation contained in this book. The author and publisher shall not be liable in any event forincidental or consequential damages in connection with, or arising out of.

the furnishing. performance. oruse of these programs.Printed in the United States of America1098765432ISBN0-13-262478-8Prentice-Hall International (UK) Limited, LondonPrentice-Hall of Australia Pty. Limited, SydneyPrentice-Hall Canada Inc., TorontoPrentice-Hall Hispanoamericana, S.A., MexicoPrentice-Hall of India Private Limited, New DelhiPrentice-Hall of Japan, Inc., TokyoSimon & Schuster Asia Pte. Ltd., SingaporeEditora Prentice-Hall do Brasil, Ltda., Rio de JaneiroTo our daughtersContentsviiPreface to the First EditionPreface to the Second EditionixIntroduction11 Sets, Relations, and Languages51.1 Sets51.2 Relations and functions 91.3 Special types of binary relations1.4 Finite and infinite sets13201.5 Three fundamental proof techniques1.6 Closures and algorithms23301.

7 Alphabets and languages 421.8 Finite representations of languagesReferences47522 Finite Automata552.1 Deterministic finite automata552.2 Nondeterministic finite automata632.3 Finite automata and regular expressions2.4 Languages that are and are not regular2.5 State minimization922.6 Algorithmic aspects of finite automataReferences75861021103 Context-free Languages3.1 Context-free grammars3.2 Parse trees1131131223.3 Pushdown automata1303.4 Pushdown automata and context-free grammars 1363.5 Languages that are and are not context-free 1433.6 Algorithms for context-free grammars1503.7 Determinism and parsingReferences 1751581794 Turing machines4.1 The definition of a Turing machine 1794.2 Computing with Turing machines 1944.3 Extensions of Turing machines 2004.4 Random access Turing machines 2104.5 Nondeterministic Turing machines 2214.6 Grammars 2274.7 Numerical functions 233References 2435 Undecidability5.1 The Church-Turing thesis 2455.2 Universal Turing machines 2475.3 The halting problem 2515.4 Unsolvable problems about Turing machines5.5 Unsolvable problems about grammars 2585.6 An unsolvable tiling problem 2625.7 Properties of recursive languages 267References 2726 Computational Complexity2452542756.1 The class P2756.2 Problems, problems.

. . 2786.3 Boolean satisfiability 2886.4 The class NP 292References 2997 NP-completeness3017.1 Polynomial-time reductions 3017.2 Cook's Theorem 3097.3 More NP-complete problems 3177.4 Coping with NP-completeness 333References 350Index353Preface to the First EditionThis book is an introuuction, on the undergraduate level, to the classical andcontemporary theory of computation. The topics covered are, in a few words,the theory of automata and formal languages, computability by Turing machinesand recursive functions, uncomputability, computational complexity, and mathematicallogic. The treatment is mathematical but the viewpoint is that of computer science; thus the chapter on context-free languages includes a discussionof parsing, and the chapters on logic establish the soundness and completenessof resolution theorem-proving.In the undergraduate curriculum, exposure to this subject tends to comelate, if at all, and collaterally with courses on the design and analysis of algorithms.

It is our view that computer science students should be exposed tothis material earlier -as sophomores or juniors- both because of the deeperinsights it yields on specific topics in computer science, and because it serves toestablish essential mathematical paradigms. But we have found teaching to arigorous undergraduate course on the subject a difficult undertaking because ofthe mathematical maturity assumed by the more advanced textbooks. Our goalin writing this book has been to make the essentials of the subject accessibleto a broad undergraduate audience in a way that is mathematically sound butpresupposes no special mathematical experience.The whole book represents about a year's worth of coursework. We haveeach taught a one-term course covering much of the material in Chapters 1through 6, omitting on various occasions and in various combinations the sections of parsing, on recursive functions, and on particular unsolvable decisionproblems.

Other selections are possible; for example, a course emphasizing computability and the foundations of mechanical logic might skip quickly over Chapters 1 through 3 and concentrate on Chapters 4, 6, 8, and 9. However, it is used,our fervent hope is that the book will contribute to the intellectual developmentPrefaceof the next generation of computer scientists by introducing them at an earlystage of their education to crisp and methodical thinking about computationalproblems.We take this opportunity to thank all from whom we have learned, bothteachers and students.

Specific thanks go to Larry Denenberg and Aaron Teminfor their proofreading of early drafts, and to Michael Kahl and Oded Shmuelifor their assistance and advice as teaching assistants. In the spring of 1980 Albert Meyer taught a course at M.LT. from a draft of this book, and we thankhim warmly for his criticisms and corrections. Of course, the blame for any remaining errors rests with us alone. Renate D' Arcangelo typed and illustrated themanuscript with her characteristic but extraordinary perfectionism and rapidity.Preface to the Second EditionMuch has changed in the fifteen years since the Elements of the Theory of Computation first appeared -and much has remained the same. Computer scienceis now a much more mature and established discipline, playing a role of ever increasing importance in a world of ubiquitous computing, globalized information,and galloping complexity -more reasons to keep in touch with its foundations.The authors of the Elements are now themselves much more mature and busy-that is why this second edition has been so long in coming.

We undertookit because we felt that a few things could be said better, a few made simpler-some even omitted altogether. More importantly, we wanted the book toreflect how the theory of computation, and its students, have evolved duringthese years. Although the theory of computation is now taught more widelyin absolute terms, its relative position within the computer science curriculum,for example vis a vis the subject of algorithms, has not been strengthened.

Infact, the field of the design and analysis of algorithms is now so mature, thatits elementary principles are arguably a part of a basic course on the theoryof computation. Besides, undergraduates today, with their extensive and earlycomputational experience, are much more aware of the applications of automatain compilers, for example, and more suspicious when simple models such as theTuring machine are presented as general computers. Evidently, the treatmentof these subjects needs some updating.Concretely, these are the major differences from the first edition:o Rudiments of the design and analysis of algorithms are introduced informally already in Chapter 1 (in connection with closures), and algorithmic questions are pursued throughout the book.

There are sections onalgorithmic problems in connection with finite automata and context-freegrammars in Chapters 2 and 3 (including state minimization and contextfree recognition), algorithms for easy variants of NP-complete problems,Prefaceooooooand a section that reviews algorithmic techniques for "coping with NPcompleteness" (special case algorithms, approximation algorithms, backtracking and branch-and-bound, local improvement, and simulated annealing algorithms).The treatment of Turing machines in Chapter 4 is more informal, and thesimulation arguments are simpler and more quantitative.

A random accessTuring machine is introduced, helping bridge the gap between the clumsiness of Turing machines and the power of computers and programminglanguages.We included in Chapter 5 On undecidability some recursive function theory (up to Rice's Theorem). Grammars and recursive numerical functionsare introduced and proved equivalent to Turing machines earlier, and theproofs are simpler. The undecidability of problems related to context-freegrammars is proved by a simple and direct argument, without recourse tothe Post correspondence problem.

We kept the tiling problem, which werevisit in the NP-completeness chapter.Complexity is done in a rather novel way: In Chapter 6, we define no othertime bounds besides the polynomial ones --thus P is the first complexityclass and concept encountered. Diagonalization then shows that there areexponential problems not in P.