INTRODUCTION TO THE THEORY OF COMPUTATION
- 1ra. edición
- United States of America CENGAGE LEARNING 2006
- 427 p Ilustración 17 x 24 cm
Preface to the First Edition To the student .. . To the educator.. The first edition.. Feedback to the author Acknowledgments . Preface to the Second Edition (International) 0 Introduction 0.1 Automata, Computability, and Complexity Complexity theory Computability theory Automata theory • .. 0.2 Mathematical Notions and Terminology Sets....・・・・・ Sequences and tuples Functions and relations Graphs . ...... Strings and languages Boolean logic. • • Summary of mathematical terms 0.3 Definitions, Theorems, and Proofs Finding proofs Part One: Automata and Languages 1 Regular Languages 1.1 Finite Automata Formal definition of a finite automaton Examples of finite automata Formal definition of computation Designing finite automata The regular operations 1.2 Nondeterminism • • • Formal definition of a nondeterministic finite automaton . . Equivalence of NFAs and DFAs Closure under the regular operations . . . . 1.3 Regular Expressions • Formal definition of a regular expression Equivalence with finite automata 1.4 Nonregular Languages. The pumping lemma for regular languages Exercises, Problems, and Solutions 2 Context-Free Languages 2.1 Context-free Grammars Formal definition of a context-free grammar Examples of context-free grammars Designing context-free grammars Ambiguity Chomsky normal form 2.2 Pushdown Automata . . Formal definition of a pushdown automaton. Examples of pushdown automata Equivalence with context-free grammars. 2.3 Non-context-free Languages The pumping lemma for context-free languages . . Exercises, Problems, and Solutions Part Two: Computability Theory 3 The Church-Turing Thesis 3.1 Turing Machines Formal definition of a Turing machine . ・・ Examples of Turing machines 3.2 Variants of Turing Machines . Multitape Turing machines Nondeterministic Turing machines . Enumerators Equivalence with other models 3.3 The Definition of Algorithm Hilbert's problems Terminology for describing Turing machines Exercises, Problems, and Solutions 4 Decidability 4.1 Decidable Languages. Decidable problems concerning regular languages 4.2 Decidable problems concerning context-free languages. The Halting Problem The diagonalization method The halting problem is undecidable A Turing-unrecognizable language Exercises, Problems, and Solutions 5 Reducibility 5.1 Undecidable Problems from Language Theory Reductions via computation histories . .. • 5.2 5.3 A Simple Undecidable Problem . .. Mapping Reducibility Computable functions Formal definition of mapping reducibility Exercises, Problems, and Solutions 6 Advanced Topics in Computability Theory 6.1 The Recursion Theorem Self-reference .... Terminology for the recursion theorem Applications
This highly anticipated revision of Michael Sipser's popular text builds upon the strengths of the previous edition. It tells the fascinating story of the theory of computation- a subject with beautiful results and exciting unsolved questions at the crossroads of mathematics and computer science. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative "proof idea" sections reveal the intuition underpinning the formal proofs of theorems by explaining profound concepts in plain English. The new edition incorporates many improvements students and professors have suggested over the years and offers completely updated, classroom tested problem sets with sample solutions at the end of each chapter. About the Author Michael Sipser has taught theoretical computer science and other mathematical subjects at the Massachusetts Institute of Technology for the past 25 years, where he is a Professor of Applied Mathematics and a member of the Computer Science ang rtificial Intelligence Laboratory (SAIL). Currently, he is the head He Man anatics Department. He enjoys teaching and pondering the many lysteries of complexity theory.