Introducing The Theory of ComputationPDF电子书下载

Part Ⅰ Regular Languages 1

1 Finite Automata 3

1.1 A Finite Automaton Has States 3

1.2 Building FAs 5

1.3 Representing FAs 9

Exercises 10

2 Regular Expressions 13

2.1 Regular Expressions 13

2.2 Kleene’s Theorem 16

2.3 Applications of REs 16

Exercises 17

3 Nondeterminism 20

3.1 Nondeterministic Finite Automata 20

3.2 What Is Nondeterminism？ 22

3.3 ε-Transitions 23

3.4 Kleene’s Theorem Revisited 24

3.5 Conversion from RE to NFA 24

3.6 Conversion from NFA to DFA 26

3.7 Conversion from FA to RE 29

Exercises 31

4 Properties of Regular Languages 34

4.1 Closure Properties 34

4.2 Distinguishable Strings 36

4.3 The Pumping Lemma 38

Exercises 40

5 Applications of Finite Automata 44

5.1 String Processing 44

5.2 Finite-State Machines 45

5.3 Statecharts 46

5.4 Lexical Analysis 46

Exercises 48

Summary 49

Interlude：JFLAP 50

Part Ⅱ Context-Free Languages 51

6 Context-Free Grammars 53

6.1 Productions 53

6.2 Further Examples 55

6.3 Derivation Trees and Ambiguity 57

6.4 Regular Languages Revisited 59

Exercises 60

7 Pushdown Automata 64

7.1 A PDA Has a Stack 64

7.2 Nondeterminism and Further Examples 67

7.3 Context-Free Languages 69

7.4 Applications of PDAs 69

Exercises 70

8 Grammars and Equivalences 73

8.1 Regular Grammars 73

8.2 The Chomsky Hierarchy 74

8.3 Usable and Nullable Variables 75

8.4 Conversion from CFG to PDA 76

8.5 An Alternative Representation 77

8.6 Conversion from PDA to CFG 78

Exercises 80

9 Properties of Context-Free Languages 83

9.1 Chomsky Normal Form 83

9.2 The Pumping Lemma：Proving Languages Not Context-Free 85

Exercises 88

10 Deterministic Parsing 91

10.1 Compilers 91

10.2 Bottom-Up Parsing 92

10.3 Table-Driven Parser for LR（1）Grammars 93

10.4 Construction of an SLR（1）Table 96

10.5 Guaranteed Parsing 100

Exercises 102

Summary 106

Interlude：Grammars in Artificial Intelligence 107

Part Ⅲ Turing Machines 109

11 Turing Machines 111

11.1 A Turing Machine Has a Tape 111

11.2 More Examples 115

11.3 TM Subroutines 117

11.4 TMs That Do Not Halt 118

Exercises 118

12 Variations of Turing Machines 122

12.1 TMs as Transducers 122

12.2 Variations on the Model 123

12.3 Multiple Tapes 124

12.4 Nondeterminism and Halting 125

12.5 Church’s Thesis 126

12.6 Universal TMs 126

Exercises 127

13 Decidable Problems and Recursive Languages 131

13.1 Recursive and Recursively Enumerable Languages 131

13.2 Decidable Questions 133

13.3 Decidable Questions about Simple Models 133

13.4 Reasoning about Computation 135

13.5 Other Models 136

Exercises 136

Summary 139

Interlude：Alternative Computers 140

Part Ⅳ Undecidability 141

14 Diagonalization and the Halting Problem 143

14.1 Self-Denial 143

14.2 Countable Sets 144

14.3 Diagonalization 145

14.4 The Halting Problem 148

Exercises 150

15 More Undecidable Problems 151

15.1 Reductions 151

15.2 Questions about TMs 152

15.3 Other Machines 154

15.4 Post’s Correspondence Problem 156

Exercises 157

16 Recursive Functions 159

16.1 Primitive Recursive Functions 159

16.2 Examples：Functions and Predicates 161

16.3 Functions That Are Not Primitive Recursive 163

16.4 Bounded and Unbounded Minimization 164

Exercises 165

Summary 167

Interlude：People 168

Part Ⅴ Complexity Theory 169

17 Time Complexity 171

17.1 Time 171

17.2 Polynomial Time 172

17.3 Examples 173

17.4 Nondeterministic Time 175

17.5 Certificates and Examples 176

17.6 P versus NP 178

Exercises 179

18 Space Complexity 181

18.1 Deterministic Space 181

18.2 Nondeterministic Space 183

18.3 Polynomial Space 183

18.4 Logarithmic Space 185

Exercises 186

19 NP-Completeness 187

19.1 NP-Complete Problems 187

19.2 Examples 188

19.3 Proving NP-Completeness by Reduction 190

Exercises 194

Summary 198

Interlude：Dealing with Hard Problems 199

References and Further Reading 201

Selected Solutions to Exercises 203

Glossary 217

Index 225