INTRODUCTION TO THE

1 INTRODUCTION TO THETHEORY OF COMPUTATION,SECOND EDITIONMICHAEL SIPSERM assachusetts Institute of TechnologyTHOMSONCOURSE TECHNOLOGYA ustralia * Canada * Mexico * Singapore * Spain * United Kingdom * United StatesTHOIVISONCOURSE TECHNOLOGYI ntroduction to the Theory of Computation,Second Editionby Michael SipserSenior Product Manager:Alyssa PrattExecutive Editor:Mac MendelsohnAssociate Production Manager:Aimee PoirierSenior Marketing Manager:Karen SeitzCOPYRIGHT 2006 ThomsonCourse Technology, a division ofThomson Learning, Inc. ThomsonLearningTM is a trademark used hereinunder in the United States of America1 2 3 45 67 89 QWT 0908070605 For more information, contactThomson Course Technology25 Thomson PlaceBoston, Massachusetts, find us on the World Wide Web RIGHTS RESERVED. No part ofthis work covered by the copyrighthereon may be reproduced or used inany form or by any means graphic,electronic, or mechanical, includingphotocopying, recording, taping, Webdistribution, or information storage andretrieval systems without the writtenpermission of the Product Manager:Mirella MisiaszekEditorial Assistant:Jennifer SmithSenior Manufacturing Coordinator:Trevor KallopCover Designer:Steve DeschesneFor permission to use material from thistext or product, submit a request onlineat additional questions aboutpermissions can be submitted by e-mail tothomsonrights~ Course Technology reservesthe right to revise this publication andmake changes from time to time in itscontent without 0-534-95097-3 CONTENTSP reface to the First edition xiTo the student.

2 XiTo the educator .. xiiThe first edition .. xiiiFeedback to the author .. xiiiAcknowledgments .. xivPreface to the Second edition xvii0 INTRODUCTION Automata, Computability, and Complexity ..1 Complexity theory .. 2 Computability theory .. 2 Automata theory .. Mathematical Notions and Terminology .. 3 Sets .. 3 Sequences and tuples .. 6 Functions and relations .. 7G raphs ..10 Strings and languages ..13 Boolean logic .. 14 Summary of mathematical terms .. Definitions, Theorems, and Proofs .. 17 Finding proofs .. Types of Proof ..21 Proof by construction .. 221 Proof by contradiction ..21 Proof by induction .. 22 Exercises, Problems, and Solutions ..25vVi CONTENTSPart One: Automata and Languages1 Regular Finite definition of a finite automaton ..Examples of finite automata ..Formal definition of computation.

3 Designing finite automata ..The regular operations .. Nondeterminism ..Formal definition of a nondeterministic finite autEquivalence of NFAs and DFAs ..Closure under the regular operations .. Regular Expressions ..Formal definition of a regular expression ..Equivalence with finite automata .. Nonregular Languages ..The pumping lemma for regular languages ..Exercises, Problems, and Solutions ..2 Context-Free Context-free Grammars ..Formal definition of a context-free grammar ..Examples of context-free grammars ..Designing context-free grammars ..Ambiguity ..Chomsky normal form .. Pushdown Automata ..Formal definition of a pushdown automaton ..Examples of pushdown automata ..Equivalence with context-free grammars .. Non-context-free Languages ..The pumping lemma for context-free , Problems, and Solutions.

4 Part Two: Computability ..29313135374041444753545863646677778299 1001021031041051061091111121151231231281 353 The Church-Turing Thesis Turing Machines .. 137 Formal definition of a Turing machine .. 139 Examples of Turing machines .. Variants of Turing Machines ..148 Multitape Turing machines ..148 Nondeterministic Turing machines ..150 Enumerators ..152 CONTENTS ViiEquivalence with other models .. The Definition of Algorithm .. 154 Hilbert's problems .. 154 Terminology for describing Turing machines ..156 Exercises, Problems, and Solutions .. 1594 Decidability Decidable Languages .. 166 Decidable problems concerning regular languages .. 166 Decidable problems concerning context-free languages .. The Halting Problem .. 173 The diagonalization method ..174 The halting problem is undecidable.

5 179A Turing-unrecognizable language ..181 Exercises, Problems, and Solutions .. 1825 Reducibility Undecidable Problems from Language Theory .. 188 Reductions via computation histories .. A Simple Undecidable Problem .. Mapping Reducibility ..206 Computable functions ..206 Formal definition of mapping reducibility .. 207 Exercises, Problems, and Solutions .. 2116 Advanced Topics in Computability Theory The Recursion Theorem ..217 Self-reference ..218 Terminology for the recursion theorem ..221 Applications .. Decidability of logical theories .. 224A decidable theory .. 227An undecidable theory .. Turing Reducibility .. A Definition of Information ..233 Minimal length descriptions .. 234 Optimality of the definition ..238 Incompressible strings and randomness .. 239 Exercises, Problems, and Solutions.

6 242 Part Three: Complexity Theory 2457 Time Complexity Measuring Complexity ..247 Big-O and small-o notation .. 248 Viii CONTENTSA nalyzing algorithms ..251 Complexity relationships among models .. The Class P ..256 Polynomial time ..256 Examples of problems in P .. The Class NP ..264 Examples of problems in NP .. 267 The P versus NP question .. NP-completeness ..271 Polynomial time reducibility .. 272 Definition of NP-completeness ..276 The Cook-Levin Theorem .. Additional NP-complete Problems .. 283 The vertex cover problem ..284 The Hamiltonian path problem .. 286 The subset sum problem .. 291 Exercises, Problems, and Solutions .. 2948 Space Complexity Savitch's Theorem .. The Class PSPACE .. PSPACE-completeness ..309 The TQBF problem ..310 Winning strategies for games ..313 Generalized geography.

7 The Classes L and NL .. NL-completeness ..323 Searching in graphs .. NL equals coNl ..326 Exercises, Problems, and Solutions .. 3289 Intractability Hierarchy Theorems .. 336 Exponential space completeness .. Relativization .. 348 Limits of the diagonalization method .. Circuit Complexity .. 351 Exercises, Problems, and Solutions .. 36010 Advanced topics in complexity theory ApproximationAlgorithms .. Probabilistic Algorithms .. 368 The class BPP ..368 Prim ality ..371 Read-once branching programs .. Alternation .. 380 Alternating time and space ..The Polynomial time hierarchy . Interactive Proof Systems ..Graph nonisomorphism ..Definition of the model ..IP = PSPACE .. Parallel Boolean circuits ..The class NC ..P-completeness .. keys ..Public-key cryptosystems ..One-way functions.

8 Trapdoor functions ..Exercises, Problems, and Solutions ..Selected BibliographyIndexCONTENTS IX38138638738738839039940040240440540540 7407409411415421 PREFACE TO THEFIRST EDITIONTO THE STUDENTW elcome!You are about to embark on the study of a fascinating and important subject:the theory of computation. It comprises the fundamental mathematical proper-ties of computer hardware, software, and certain applications thereof. In study-ing this subject we seek to determine what can and cannot be computed, howquickly, with how much memory, and on which type of computational subject has obvious connections with engineering practice, and, as in manysciences, it also has purely philosophical know that many of you are looking forward to studying this material butsome may not be here out of choice.

9 You may want to obtain a degree in com-puter science or engineering, and a course in theory is required-God knowswhy. After all, isn't theory arcane, boring, and worst of all, irrelevant?To see that theory is neither arcane nor boring, but instead quite understand-able and even interesting, read on. Theoretical computer science does havemany fascinating big ideas, but it also has many small and sometimes dull detailsthat can be tiresome. Learning any new subject is hard work, but it becomeseasier and more enjoyable if the subject is properly presented. My primary ob-jective in writing this book is to expose you to the genuinely exciting aspects ofcomputer theory, without getting bogged down in the drudgery. Of course, theonly way to determine whether theory interests you is to try learning PREFACE TO THE FIRST EDITIONT heory is relevant to practice.

10 It provides conceptual tools that practition-ers use in computer engineering. Designing a new programming language for aspecialized application? What you learned about grammars in this course comesin handy. Dealing with string searching and pattern matching? Rememberfiniteautomata and regular expressions. Confronted with a problem that seems to re-quire more computer time than you can afford? Think back to what you learnedabout NP-completeness. Various application areas, such as modern cryptographicprotocols, rely on theoretical principles that you will learn also is relevant to you because it shows you a new, simpler, and moreelegant side of computers, which we normally consider to be complicated ma-chines. The best computer designs and applications are conceived with elegancein mind. A theoretical course can heighten your aesthetic sense and help youbuild more beautiful , theory is good for you because studying it expands your mind.