Introductiontothetheoryofcomputation

计算理论：计算复杂性的形式化描述、自动机、图灵机等有关算法复杂性的理论问题Introduction to the theory ofCOMPUTATIONTHIRD EDITIONMICHAEL SIPSERCENGAGELearningaustralia· Brazil. Japan· Korea· Mexico· Singapore· Spain. United Kingdom· United StatesCopyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from thecontent at any time if subsequent rights restrictions require itCENGAgEearnIngntroduction to the theory ofC 2013 Cengage LearningComputation, Third EditionALL RIGHTS RESERVED. No part of this work covered by the copyMichael Sipserright herein may be reproduced, transmitted, stored or used in anyEditor-in-Chief: Marie Leeform or by any means graphic, electronic, or mechanical, includingSenior Product Manager:but not limited to photocopying, recording, scanning, digitizing, tapAlyssa Pratting, Web distribution, information networks, or information storageAssociate Product Manager:and retrieval systems, except as permitted under Section 107 or 108Stephanie Lorenzof the 1976 United States Copyright Act, without the prior writtenContent project managerpermission of the publisher States Copyright Act, without the priorJennifer Feltri-Georgewritten permission of the publisher.Art Director GEX Publishing ServicesAssociate Marketing Manager:For product information and technology assistance, contact us atShanna SheltonCengage Learning Customer& Sales Support,Cover Designer: Wing-ip Ngan1-800-354-9706Ink design, inFor permission to use material from this text or product,Cover Image Credit: @Superstockit all requests online at cengage. com/permissionsFurther permissions questions can be emailed topermissionrequest@cengage.comess Control number: 2012938665SBN-13:978-1-133-18779-0SBN-10:1-133-18779Xt0 Channel Center streetBoston MA 02210Cengage Learning is a leading provider of cutions with office locations around the globe, including Singapore, theUnited Kingdom, Australia, Mexico, Brazil, and Japalocal office at: international cengage. com/regionCengage Learning products are represented in Canada by NelsonEducation LtdForyourlifelonglearningsolutionsvisitwww.cengage.comCengage Learning reserves the right to revise this publication andmake changes from time to time in its content without notice.The programs in this book are for instructional purposes onlyThey have been tested with care, but are not guaranteed for anyparticular intent beyond educational purposes. The author andthe publisher do nonor do they accept any liabilities with respect to the programsPrinted in the united states of america123456781615141312Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from theeBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additionalTo Ina. Rachel and aaronCopyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from theeBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additionalcontent at any time if subsequent rights restrictions require itCopyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from theeBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additionalcontent at any time if subsequent rights restrictions require itNTENTPreface to the first editionTo the studentTo the educatorX11The first edition,,,,.,X111Feedback to the authorAcknowledgments,....XIVPreface to the Second editionXVIIPreface to the Third edition0 Introduction0.1 Automata, Computability, and ComplexityComplexity theoryComputability theoryAutomata theo0. 2 Mathematical Notions and Terminologyetsequences and tuples6Functions and relations10Strings and languagesBgIc14Summary of mathematical terms16Finding proot ems, ar0.3 Definitions. Theorems and Proofs0.4 Types of proof21Proof by constructionProof by contradictionProof by induction22Exercises. Problems. and solutionsCopyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from theeBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additionalcontent at any time if subsequent rights restrictions require itCONTENTSPart One: Automata and languages291 Regular languages311.1 Finite automata31Formal definition of a finite automaton35Examples of finite automata,,,..37Formal definition of computationDesigning finite automata41The regular operations1.2 Nondeterminism47Formal definition of a nondeterministic finite automatonEquivalence of nfas and dfas54Closure under the regular operations.....581.3 Regular expressions63Formal definition of a regular expressionEquivalence with finite automata661. 4 Nonregular languasgThe pumping lemma for regular languagesEProblems, and solution822 Context-Free Languages1012. 1 Context-Free grammars102Formal definition of a context-free grammar..104Examples of context-free grammars ............ 105esigning context-free grammars106Ambiguity:·107Chomsky normal form2.2 Pushdown automataFormal definition of a pushdown automaton...........113Examples of pushdown automata114Equivalence with context-free grammars1172.3 Non-Context-Free languages125The pumping lemma for context-free languages1252.4 Deterministic Context-Free Languages...............130Properties of dcfls133Deterministic context-free grammars135Relationship of pDas and dcFgs146Parsing and lr(k) grammars151Exercises. Problems, and Solutions................... 154Part Two: Computability Theory1633 The Church-Turing ThesIs1653.1 Turing Machines165Formal definition of a Turing machine167Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from theeBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additionalcontent at any time if subsequent rights restrictions require itCONTENTSExamples of Turing machines1703. 2 Variants of Turing Machines176Multitape turing machines176Nondeterministic Turing machines178Enumerators180Equivalence with other models1813.3 The Definition of Algorithm18Hilbert's problems,,182Terminology for describing Turing machines184Exercises. Problems and solutions1874 Decidability1934. 1 Decidable languages194Decidable problems concerning regular languages.194Decidable problems concerning context-free languages1984.2 Undecidabilit20The diagonalization method,,,202An undecidable language207A Turing-unrecognizable language,209ed soluti2105 Reducibility2155. 1 Undecidable Problems from Language theory216Reductions via computation histories,,,2205.2 A Simple Undecidable Problem..2275.3 Mapping reducibility234Computable functio34Formal definition of mapping reducibility...235Problems. and soluti2396 Advanced Topics in Computability Theory2456.1 The recursion theorem,,,,,,245Self-reference246Terminology for the recursion theorem...249Applations2506.2 Decidability of logical theories252a decidable theoryAn undecidable theory2576.3 Turing reducibili2606. 4 A Definition of Information..................... 261Minimal length descriptions262Optimality of the definition266Incompressible strings and randomness.267Exercises, Problems, and solutions270Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from theeBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additionalcontent at any time if subsequent rights restrictions require itV CONTENTSPart Three: Complexity Theory2737 Time Complexity2757.1 Measuring Complexity275Big-O and small-o notation..276Analyzing algorithms279Complexity relationships among models2827.2 The Class p284Polynomial time284Examples of problems in P,2867.3 The Class np292Examples of problems in NP295The P versus NP question2977.4 NP-completenessPolynomial time reducibility300Definition of NP-completeness..................304The Cook-Levin theorem3047.5 Additional NP-complete Problems311The vertex cover problem312The Hamiltonian pathroblem..314The subset sum problem319Exercises. Problems, and solutions3228 Space Complexity3318. 1 Savitch's Theorem,3338.2 The Class pspace,3368.3 PSPACE-completeness337The TQBF probleem..338Winning strategies for games..341Generalized geography.3438.4 The Classes l and Nl3488.5 NL-completeness351Searching in graphs..3538.6 NL equals CoNL354Exercises. Problems. and solutions9 Intractability3639. 1 Hierarchy Theorems.....364Exponential space completeness.3719.2 RelativizationLimits of the diagonalization method376..3779.3 Circuit Complexity..,379Exercises. Problems and solutions38810 Advanced Topics in Complexity Theory39310.1 Approximation algorithms.....393Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from theeBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additionalcontent at any time if subsequent rights restrictions require it