Sold Out
Book Categories |
1 Mathematical Preliminaries 1
1.1 Introduction 1
1.2 Sets 1
1.3 Relations and Graphs 3
1.4 Functions and Counting 8
1.5 Proof Techniques 16
1.6 Summary and Problems 25
2 Regular Languages 31
2.1 Introduction 31
2.2 Language Basics 32
2.3 Regular Expressions 36
2.4 Regular Grammars 40
2.5 Deterministic Finite Automata 45
2.6 Nondeterministic Finite Automata 55
2.7 Summary and Additional Problems 64
3 Equivalences 69
3.1 Introduction 69
3.2 NFA to DFA 69
3.3 Finite Automata and Regular Grammars 76
3.4 Regular Expression to NFA 79
3.5 NFA to Regular Expression 82
3.6 Summary and Additional Problems 90
4 Structure of Regular Languages 93
4.1 Introduction 93
4.2 Closure Properties 94
4.3 Nonregular Languages 98
4.4 Myhill-Nerode Theorem 105
4.5 State Minimization 110
4.6 Summary and Additional Problems 119
5 Context-free Languages 125
5.1 Introduction 125
5.2 Context-free Grammars 125
5.3 Parse Trees 132
5.4 Ambiguity 137
5.5 Eliminating Ugly Productions 141
5.6 Normal Forms 147
5.7 Summary and Additional Problems 155
6 Structure of CFLs 159
6.1 Introduction 159
6.2 Pushdown Automata 159
6.3 CFG and PDA 169
6.4 Pumping Lemma 175
6.5 Closure Properties of CFLs 182
6.6 Deterministic Pushdown Automata 186
6.7 Summary and Additional Problems 191
7 Computably Enumerable Languages 201
7.1 Introduction 201
7.2 Unrestricted Grammars 201
7.3 Turing Machines 205
7.4 Acceptance and Rejection 210
7.5 Using Old Machines 217
7.6 Multitape TMs 228
7.7 Nondeterministic TMs and Grammars 233
7.8 Summary and Additional Problems 240
8 A Noncomputably Enumerable Language 245
8.1 Introduction 245
8.2Turing Machines as Computers 246
8.3 TMs as Language Deciders 251
8.4 How Many Machines? 257
8.5 Acceptance Problem 261
8.6 Chomsky Hierarchy 267
8.7 Summary and Additional Problems 272
9 Algorithmic Solvability 281
9.1 Introduction 281
9.2 Problem Reduction 282
9.3 Rice's Theorem 287
9.4 About Finite Automata 293
9.5 About PDA 295
9.6 Post's Correspondence Problem 301
9.7 About Logical Theories 307
9.8 Other Interesting Problems 314
9.9 Summary and Additional Problems 316
10 Computational Complexity 327
10.1 Introduction 327
10.2 Rate of Growth of Functions 328
10.3 Complexity Classes 333
10.4 Space Complexity 338
10.5 Time Complexity 342
10.6 The Class NP 348
10.7 NP-Completeness 352
10.8 Some NP-Complete Problems 358
10.9 Dealing with NP-Complete Problems 369
10.10 Summary and Additional Problems 372
Answers and Hints to Selected Problems 385
References 407
Index 415
Login|Complaints|Blog|Games|Digital Media|Souls|Obituary|Contact Us|FAQ
CAN'T FIND WHAT YOU'RE LOOKING FOR? CLICK HERE!!! X
You must be logged in to add to WishlistX
This item is in your Wish ListX
This item is in your CollectionElements of Computation Theory
X
This Item is in Your InventoryElements of Computation Theory
X
You must be logged in to review the productsX
X
X
Add Elements of Computation Theory, As Computer Science progressively matures as an established discipline, it becomes increasingly important to revisit its theoretical foundations, learn the appropriate techniques for answering theory-based questions, and build one's confidence in implemen, Elements of Computation Theory to the inventory that you are selling on WonderClubX
X
Add Elements of Computation Theory, As Computer Science progressively matures as an established discipline, it becomes increasingly important to revisit its theoretical foundations, learn the appropriate techniques for answering theory-based questions, and build one's confidence in implemen, Elements of Computation Theory to your collection on WonderClub |