Fundamentals of the Theory of Computation : Principles and Practice

, by Greenlaw, Raymond; Hoover, H. James

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9781558604742 | 155860474X
Cover: Hardcover
Copyright: 5/1/1998

Rent

(Recommended)

$48.63

Term

Due

Price

Semester

Dec 13

$54.03

Quarter

Aug 30

$51.34

Short Term

Jul 26

$48.63

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping cart.
Buy New

Usually Ships in 3-5 Business Days

$73.83
eBook

Available Instantly

Online: 1825 Days

Downloadable: Lifetime Access

$87.69

This innovative textbook presents the key foundational concepts that can be covered in a one semester undergraduate course in the theory of computation. It offers the most accessible and motivational course material available for undergraduate computer theory classes and is directed at the typical undergraduate who may have difficulty understanding the relevance of the course to their future careers. The text helps make students more comfortable with techniques required for the deeper study of computer science.This text is a bridge between theory and practice. It shows how theory is motivated by practical problems, and in turn how theory influences the practice of computing. Simple tools like string matchers, complex tools like compilers, and general notions like cryptographic security all lie at the interface between principles and practice.

Preface

xiii

1 Introduction

(18)

1.1 Some Computing Puzzles

(12)

1.1.1 A Restricted Version of the C Language

(1)

1.1.2 Problem 1 Detecting Strings in a Language

(1)

1.1.3 Problem 2 Execution Configuration

(2)

1.1.4 Problem 3 Deducing Behavior from Structure

(4)

1.1.5 Problem 4 The Halting Problem

(3)

1.2 What Is Computability?

(2)

1.3 Related Works

(1)

1.4 Overview of This Book

(1)

1.5 Exercises

(2)

2 Languages and Problems

(46)

2.1 Introduction

(4)

2.2 Symbols, Alphabets, and Strings

(5)

2.2.1 Strings

(1)

2.2.2 Lexicographical and Enumeration Ordering

(1)

2.2.3 String Concatenation

(1)

2.2.4 Parts of Strings

(1)

2.2.5 String Reversal

(1)

2.3 Languages

(2)

2.4 Operations on Languages

(5)

2.4.1 Union

(1)

2.4.2 Complementation

(1)

2.4.3 Intersection

(1)

2.4.4 Symmetric Difference

(1)

2.4.5 DeMorgan's Laws

(1)

2.4.6 Length Subsetting

(1)

2.4.7 Concatenation

(1)

2.4.8 Reversal

(1)

2.4.9 Kleene Star

(1)

2.5 Alphabet Encodings

(4)

2.6 Some Test Languages

(1)

2.7 How Many Languages Are There?

(3)

2.7.1 Most Languages Do Not Have Compilers

(1)

2.8 Problem Representations

(3)

2.9 Types of Problems

(7)

2.9.1 Representing Graphs

(2)

2.9.2 Spanning Trees

(2)

2.9.3 Decision Problems

(1)

2.9.4 Function Problems

(1)

2.9.5 Search Problems

(1)

2.10 Casting Problems into Languages

(1)

2.11 Decision, Search, and Enumeration

(2)

2.12 Language Operations and Enumeration

(1)

2.13 Exercises

(9)

3 Regular Expressions and Languages

(18)

3.1 Introduction

(2)

3.2 Regular Languages and Constructions

(2)

3.3 Regular Expressions

(4)

3.3.1 The Grammar of Standard Regular Expressions

(1)

3.3.2 Examples of Standard Regular Expressions

(1)

3.3.3 Consistency and Completeness of Standard Regular Expressions

(1)

3.4 Not All Languages Are Regular

(1)

3.5 Applications of Regular Expressions

(5)

3.5.1 Validation

(2)

3.5.2 Search and Selection

(2)

3.5.3 Tokenization

(1)

3.6 Exercises

(4)

4 Fundamental Machines Part I: Finite-State Control Machines

(38)

4.1 Introduction

(2)

4.1.1 The Church-Turing Thesis

(1)

4.2 Basic Machine Notions

(5)

4.2.1 Tapes

(3)

4.2.2 Finite Controls

(1)

4.3 Deterministic Finite Automata

(13)

4.3.1 DFA Design

100

(3)

4.4 Nondeterministic Finite Automata

103

(4)

4.5 Equivalence of DFAs and NFAs

107

(8)

4.6 Equivalence of DFAs and C-- Programs

115

(1)

4.7 Exercises

116

(5)

5 Properties of Finite-State Languages

121

(34)

5.1 Introduction

121

(1)

5.2 Machines for Five Language Operations

122

(10)

5.2.1 Closure under Complement

123

(2)

5.2.2 Closure under Union

125

(2)

5.2.3 Closure under Intersection

127

(1)

5.2.4 Closure under Concatenation

128

(2)

5.2.5 Closure under Kleene Star

130

(2)

5.3 Equivalence of Regular Expressions and Finite Automata

132

(10)

5.4 Pumping Lemma for Regular Languages

142

(3)

5.5 Applications of the Pumping Lemma

145

(2)

5.6 Using Closure Properties to Deduce That a Language Is Nonregular

147

(1)

5.7 Exercises

148

(7)

6 Fundamental Machines Part II: Stack and Tape Machines

155

(40)

6.1 Pushdown Automata

155

(8)

6.1.1 Deterministic Pushdown Automata

156

(4)

6.1.2 Nondeterministic Pushdown Automata

160

(1)

6.1.3 Inequivalence of DPDAs and PDAs

161

(2)

6.2 Turing Machines

163

(24)

6.2.1 Deterministic Turing Machines

165

(10)

6.2.2 Multiple-Work-Tape Turing Machines

175

(5)

6.2.3 Nondeterministic Turing Machines

180

(4)

6.2.4 Equivalence of DTMs and NTMs

184

(3)

6.3 Undecidable Languages

187

(1)

6.4 Relations among Language Classes

188

(1)

6.5 Exercises

189

(6)

7 Grammars

195

(26)

7.1 Introduction

195

(1)

7.2 Regular Grammars

195

(4)

7.3 Context-Free Grammars

199

(5)

7.4 Closure Properties of Context-Free Languages

204

(2)

7.5 Parsing with Nondeterministic Pushdown Automata

206

(2)

7.6 Parsing with Deterministic Pushdown Automata

208

(1)

7.7 Parse Trees and Attribution

209

(3)

7.8 Languages That Are Not Context-Free

212

(4)

7.9 Exercises

216

(5)

8 Computational Complexity

221

(20)

8.1 Introduction

221

(1)

8.2 Asymptotic Notation

222

(3)

8.3 Time and Space Complexity

225

(4)

8.4 Simulations

229

(5)

8.5 Reducibilities

234

(3)

8.5.1 Many-One Reducibility

235

(2)

8.6 Exercises

237

(4)

9 Circuit Complexity

241

(18)

9.1 Introduction

241

(1)

9.2 The Boolean Circuit Model of Computation

242

(5)

9.3 Circuit Resources

247

(3)

9.3.1 Uniform Circuit Families

248

(2)

9.4 Examples of Boolean Circuits

250

(3)

9.5 The Complexity Class NC

253

(1)

9.6 Exercises

254

(5)

10 Feasible Problems

259

(28)

10.1 Introduction

259

(2)

10.2 Polynomial Time

261

(2)

10.3 P-Completeness Theory

263

(2)

10.4 Examples of P-Complete Problems

265

(8)

10.4.1 Generic Machine Simulation

265

(2)

10.4.2 The Circuit Value Problem and Some Variants

267

(6)

10.5 P-Complete Problems and Reductions

273

(9)

10.5.1 NAND Circuit Value Problem

274

(2)

10.5.2 Context-Free Grammar Nonempty

276

(3)

10.5.3 Lexicographically First Maximal Independent Set

279

(3)

10.6 Exercises

282

(5)

11 Intractable Problems

287

(32)

11.1 Introduction

287

(1)

11.2 Nondeterministic Polynomial Time

288

(4)

11.3 NP-Completeness Theory

292

(2)

11.4 Examples of NP-Complete Problems

294

(6)

11.4.1 Satisfiability and Some Variants

294

(4)

11.4.2 Hamiltonian Circuit Problem

298

(2)

11.5 NP-Complete Problems and Reductions

300

(13)

11.5.1 Traveling Salesperson Problem

300

(4)

11.5.2 Vertex Cover

304

(4)

11.5.3 Three-Dimensional Matching

308

(5)

11.6 Exercises

313

(6)

Appendix A Notation

319

(2)

Appendix B Greek Alphabet

321

(2)

Bibliography

323

(4)

Index

327

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Fundamentals of the Theory of Computation : Principles and Practice

Summary

Table of Contents

Supplemental Materials