Introduction to the Theory of ComputationMichael Sipser's philosophy in writing this book is simple: make the subject interesting and relevant, and the students will learn. His emphasis on unifying computer science theory - rather than offering a collection of low-level details - sets the book apart, as do his intuitive explanations. Throughout the book, Sipser - a noted authority on the theory of computation - builds students' knowledge of conceptual tools used in computer science, the aesthetic sense they need to create elegant systems, and the ability to think through problems on their own. INTRODUCTION TO THE THEORY OF COMPUTATION provides a mathematical treatment of computation theory grounded in theorems and proofs. Proofs are presented with a "proof idea" component to reveal the concepts underpinning the formalism. Algorithms are presented using prose instead of pseudocode to focus attention on the algorithms themselves, rather than on specific computational models. Topic coverage, terminology, and order of presentation are traditional for an upper-level course in computer science theory. Users of the Preliminary Edition (now out of print) will be interested to note several new chapters on complexity theory: Chapter 8 on space complexity; Chapter 9 on provable intractability, and Chapter 10 on advanced topics, including approximation algorithms, alternation, interactive proof systems, cryptography, and parallel computing. |
From inside the book
70 pages matching regular languages in this book
Page 388
Where's the rest of this book?
Results 1-3 of 70
Contents
Introduction | 1 |
Decidability | 4 |
Summary of mathematical terms | 16 |
Copyright | |
17 other sections not shown
Other editions - View all
Common terms and phrases
A₁ accept alphabet arrows automata binary Boolean circuit Boolean formula branch c₁ called circuit clause computation history configuration construct contains context-free grammar context-free language convert corresponding decidable define describe deterministic directed graph edges empty stack encoding equivalent example exponential finite automaton following figure give GNFA halts Hence input string labeled log space M₁ move N₁ natural numbers nondeterministic finite automaton nondeterministic Turing machine notation NP-complete number of nodes operation oracle output parse tree Player polynomial polynomial time algorithm polynomial time reducible probabilistic problem PROOF IDEA prove PSPACE PSPACE-complete pumping lemma pumping length pushdown automaton q₁ quantifiers R₁ recognizes regular expression regular languages reject runs satisfying assignment Savitch's theorem sequence simulation space complexity stage steps strings of length tape testing transition function true Turing machine Turing-recognizable undecidable variables Verifier