Introduction to automata theory, languages, and computation

Preface v......Page 3
Contents vii......Page 5
1.1 Strings, alphabets, and languages 1......Page 9
1.2 Graphs and trees 2......Page 10
1.3 Inductive proofs 4......Page 12
1.4 Set notation 5......Page 13
1.5 Relations 6......Page 14
1.6 Synopsis of the book 8......Page 16
2.1 Finite state systems 13......Page 21
2.2 Basic definitions 16......Page 24
2.3 Nondeterministic finite automata 19......Page 27
2.4 Finite automata with ε-moves 24......Page 32
2.5 Regular expressions 28......Page 36
2.6 Two-way finite automata 36......Page 44
2.7 Finite automata with output 42......Page 50
2.8 Applications of finite automata 45......Page 53
3.1 The pumping lemma for regular sets 55......Page 63
3.2 Closure properties of regular sets 58......Page 66
3.3 Decision algorithms for regular sets 63......Page 71
3.4 The Myhill-Nerode theorem and minimization of finite automata 65......Page 73
4.1 Motivation and introduction 77......Page 85
4.2 Context-free grammars 79......Page 87
4.3 Derivation trees 82......Page 90
4.4 Simplification of context-free grammars 87......Page 95
4.5 Chomsky normal form 92......Page 100
4.6 Greibach normal form 94......Page 102
4.7 The existence of inherently ambiguous context-free languages 99......Page 107
5.1 Informal description 107......Page 115
5.2 Definitions 108......Page 116
5.3 Pushdown automata and context-free languages 114......Page 122
6.1 The pumping lemma for CFL\'s 125......Page 133
6.2 Closure properties of CFL\'s 130......Page 138
6.3 Decision algorithms for CFL\'s 137......Page 145
7.1 Introduction 146......Page 154
7.2 The Turing machine model 147......Page 155
7.3 Computable languages and functions 150......Page 158
7.4 Techniques for Turing machine construction 153......Page 161
7.5 Modifications of Turing machines 159......Page 167
7.6 Church\'s hypothesis 166......Page 174
7.7 Turing machines as enumerators 167......Page 175
7.8 Restricted Turing machines equivalent to the basic model 170......Page 178
8.1 Problems 177......Page 185
8.2 Properties of recursive and recursively enumerable languages 179......Page 187
8.3 Universal Turing machines and an undecidable problem 181......Page 189
8.4 Rice\'s theorem and some more undecidable problems 185......Page 193
8.5 Undecidability of Post\'s correspondence problem 193......Page 201
8.6 Valid and invalid computations of TM\'s: a tool for proving CFL problems undecidable 201......Page 209
8.7 Greibach\'s theorem 205......Page 213
8.8 Introduction to recursive function theory 207......Page 215
8.9 Oracle computations 209......Page 217
9.1 Regular grammars 217......Page 225
9.2 Unrestricted grammars 220......Page 228
9.3 Context-sensitive languages 223......Page 231
9.4 Relations between classes of languages 227......Page 235
10 Deterministic Context-Free Languages 233......Page 241
10.1 Normal forms for DPDA\'s 234......Page 242
10.2 Closure of DCFL\'s under complementation 235......Page 243
10.3 Predicting machines 240......Page 248
10.4 Additional closure properties of DCFL\'s 243......Page 251
10.5 Decision properties of DCFL\'s 246......Page 254
10.6 LR(0) grammars 248......Page 256
10.7 LR(0) grammars and DPDA\'s 252......Page 260
10.8 LR(k) grammars 260......Page 268
11.1 Trios and full trios 270......Page 278
11.2 Generalized sequential machine mappings 272......Page 280
11.3 Other closure properties of trios 276......Page 284
11.4 Abstract families of languages 277......Page 285
11.6 Summary 279......Page 287
12.1 Definitions 285......Page 293
12.2 Linear speed-up, tape compression, and reductions in the number of tapes 288......Page 296
12.3 Hierarchy theorems 295......Page 303
12.4 Relations among complexity measures 300......Page 308
12.5 Translational lemmas and nondeterministic hierarchies 302......Page 310
12.6 Properties of general complexity measures: the gap, speedup, and union theorems 306......Page 314
12.7 Axiomatic complexity theory 312......Page 320
13.1 Polynomial time and space 320......Page 328
13.2 Some NP-complete problems 324......Page 332
13.3 The class co-NP 341......Page 349
13.4 PSPACE-complete problems 343......Page 351
13.5 Complete problems for P and NSPACE(log n) 347......Page 355
13.6 Some provably intractable problems 350......Page 358
13.7 The P=NP question for Turing machines with oracles: limits on our ability to tell whether P=NP 362......Page 370
14.1 Auxiliary pushdown automata 377......Page 385
14.2 Stack automata 381......Page 389
14.3 Indexed languages 389......Page 397
14.4 Developmental systems 390......Page 398
Bibliography 396......Page 404
Index 411......Page 419