INTRODUCTION TO THE THEORY OF COMPUTATION

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.

Ingeniería en Tecnologías de la Información y Comunicaciones