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