Preface to the First Edition 

xi  
To the student 

xi  
To the educator 

xii  
The first edition 

xiii  
Feedback to the author 

xiii  
Acknowledgments 

xiv  
Preface to the Second Edition 

xvii  


1  (28) 

Automata, Computability, and Complexity 


1  (2) 


2  (1) 


2  (1) 


3  (1) 

Mathematical Notions and Terminology 


3  (14) 


3  (3) 


6  (1) 


7  (3) 


10  (3) 


13  (1) 


14  (2) 

Summary of mathematical terms 


16  (1) 

Definitions, Theorems, and Proofs 


17  (4) 


17  (4) 


21  (8) 


21  (1) 


21  (1) 


22  (3) 

Exercises, Problems, and Solutions 


25  (4) 

Part One: Automata and Languages 


29  (106) 


31  (68) 


31  (16) 

Formal definition of a finite automaton 


35  (2) 

Examples of finite automata 


37  (3) 

Formal definition of computation 


40  (1) 

Designing finite automata 


41  (3) 


44  (3) 


47  (16) 

Formal definition of a nondeterministic finite automaton 


53  (1) 

Equivalence of NFAs and DFAs 


54  (4) 

Closure under the regular operations 


58  (5) 


63  (14) 

Formal definition of a regular expression 


64  (2) 

Equivalence with finite automata 


66  (11) 


77  (22) 

The pumping lemma for regular languages 


77  (5) 

Exercises, Problems, and Solutions 


82  (17) 


99  (36) 


100  (9) 

Formal definition of a contextfree grammar 


102  (1) 

Examples of contextfree grammars 


103  (1) 

Designing contextfree grammars 


104  (1) 


105  (1) 


106  (3) 


109  (14) 

Formal definition of a pushdown automaton 


111  (1) 

Examples of pushdown automata 


112  (3) 

Equivalence with contextfree grammars 


115  (8) 

Noncontextfree Languages 


123  (12) 

The pumping lemma for contextfree languages 


123  (5) 

Exercises, Problems, and Solutions 


128  (7) 

Part Two: Computability Theory 


135  (110) 


137  (28) 


137  (11) 

Formal definition of a Turing machine 


139  (3) 

Examples of Turing machines 


142  (6) 

Variants of Turing Machines 


148  (6) 

Multitape Turing machines 


148  (2) 

Nondeterministic Turing machines 


150  (2) 


152  (1) 

Equivalence with other models 


153  (1) 

The Definition of Algorithm 


154  (11) 


154  (2) 

Terminology for describing Turing machines 


156  (3) 

Exercises, Problems, and Solutions 


159  (6) 


165  (22) 


166  (7) 

Decidable problems concerning regular languages 


166  (4) 

Decidable problems concerning contextfree languages 


170  (3) 


173  (14) 

The diagonalization method 


174  (5) 

The halting problem is undecidable 


179  (2) 

A Turingunrecognizable language 


181  (1) 

Exercises, Problems, and Solutions 


182  (5) 


187  (30) 

Undecidable Problems from Language Theory 


188  (11) 

Reductions via computation histories 


192  (7) 

A Simple Undecidable Problem 


199  (7) 


206  (11) 


206  (1) 

Formal definition of mapping reducibility 


207  (4) 

Exercises, Problems, and Solutions 


211  (6) 

Advanced Topics in Computability Theory 


217  (28) 


217  (7) 


218  (3) 

Terminology for the recursion theorem 


221  (1) 


222  (2) 

Decidability of logical theories 


224  (8) 


227  (2) 


229  (3) 


232  (1) 

A Definition of Information 


233  (12) 

Minimal length descriptions 


234  (4) 

Optimality of the definition 


238  (1) 

Incompressible strings and randomness 


239  (3) 

Exercises, Problems, and Solutions 


242  (3) 

Part Three: Complexity Theory 


245  (170) 


247  (56) 


247  (9) 

BigO and smallo notation 


248  (3) 


251  (3) 

Complexity relationships among models 


254  (2) 


256  (8) 


256  (2) 

Examples of problems in P 


258  (6) 


264  (7) 

Examples of problems in NP 


267  (2) 


269  (2) 


271  (12) 

Polynomial time reducibility 


272  (4) 

Definition of NPcompleteness 


276  (1) 


276  (7) 

Additional NPcomplete Problems 


283  (20) 


284  (2) 

The Hamiltonian path problem 


286  (5) 


291  (3) 

Exercises, Problems, and Solutions 


294  (9) 


303  (32) 


305  (3) 


308  (1) 


309  (11) 


310  (3) 

Winning strategies for games 


313  (2) 


315  (5) 


320  (3) 


323  (3) 


325  (1) 


326  (9) 

Exercises, Problems, and Solutions 


328  (7) 


335  (30) 


336  (12) 

Exponential space completeness 


343  (5) 


348  (3) 

Limits of the diagonalization method 


349  (2) 


351  (14) 

Exercises, Problems, and Solutions 


360  (5) 

Advanced topics in complexity theory 


365  (50) 


365  (3) 


368  (12) 


368  (3) 


371  (5) 

Readonce branching programs 


376  (4) 


380  (7) 

Alternative time and space 


381  (5) 

The Polynomial time hierarchy 


386  (1) 

Interactive Proof Systems 


387  (12) 


387  (1) 


388  (2) 


390  (9) 


399  (6) 


400  (2) 


402  (2) 


404  (1) 


405  (10) 


405  (2) 


407  (1) 


407  (2) 


409  (2) 

Exercises, Problems, and Solutions 


411  (4) 
Selected Bibliography 

415  (6) 
Index 

421  