An edition of Introduction to automata theory, languages, and computation (1979)

Introduction to automata theory, languages, and computation

by John E. Hopcroft, Jeffrey D. Ullman, and Rajeev Motwani

★★★★ ★ 4.50 ·
2 Ratings
36 Want to read
4 Currently reading
2 Have read

Cover of: Introduction to automata theory, languages, and computation by

Not in Library

My Reading Lists:

Use this Work

Create a new list

★★★★ ★ 4.50 ·
2 Ratings
36 Want to read
4 Currently reading
2 Have read

Check nearby libraries

Buy this book

Last edited by OL-00

February 25, 2024 | History

Edit

An edition of Introduction to automata theory, languages, and computation (1979)

Introduction to automata theory, languages, and computation

by John E. Hopcroft, Jeffrey D. Ullman, and Rajeev Motwani

★★★★ ★ 4.50 ·
2 Ratings
36 Want to read
4 Currently reading
2 Have read

This edition doesn't have a description yet. Can you add one?

Publish Date

2007

Publisher

Pearson/Addison-Wesley, Pearson/Addison Wesley

Pages

535

Check nearby libraries

Buy this book

Previews available in: German English

Showing 6 featured editions. View all 6 editions?

Edition	Availability
1 Introduction to automata theory, languages, and computation 2007, Pearson/Addison-Wesley, Pearson/Addison Wesley Hardcover 0321455363 9780321455369	aaaa Not in Library Libraries near you: WorldCat
2 Introduction to Automata Theory, Languages, and Computation (3rd Edition) July 8, 2006, Addison Wesley Hardcover in English - 3 edition 0321455363 9780321455369	zzzz Not in Library Libraries near you: WorldCat
3 Introduction to Automata Theory, Languages, and Computation 2003, Pearson Education, Limited in English 0321210298 9780321210296	zzzz Not in Library Libraries near you: WorldCat
4 Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie 2002, Pearson Education Deutschland in German - 2., überarbeitete Auflage 3827370205 9783827370204	zzzz Not in Library Libraries near you: WorldCat
5 Introduction to automata theory, languages, and computation 2001, Addison-Wesley in English - 2nd ed. 0201441241 9780201441246	zzzz Not in Library Libraries near you: WorldCat
6 Introduction to automata theory, languages, and computation 1979, Addison-Wesley in English 020102988X 9780201029888	eeee Preview Only Preview Book ×Close Libraries near you: WorldCat

Add another edition?

Book Details

Published in

USA

1. Automata: The Methods and the Madness Page 1

1.1. Why Study Automata Theory Page 2

1.1.1. Introduction to Finite Automata Page 2

1.1.2. Structural Representations Page 4

1.1.3. Automata and Complexity Page 5

1.2. Introduction to Formal Proof Page 5

1.2.1. Deductive Proofs Page 6

1.2.2. Reduction to Definitions Page 8

1.2.3. Other Theorem Forms Page 10

1.2.4. Theorems That Appear Not to Be If-Then Statements Page 13

1.3. Additional Forms of Proof Page 13

1.3.1. Proving Equivalences About Sets Page 14

1.3.2. The Contrapositive Page 14

1.3.3. Proof by Contradiction Page 16

1.3.4. Counterexamples Page 17

1.4. Inductive Proofs Page 19

1.4.1. Induction on Integers Page 19

1.4.2. More General Forms of Integer Inductions Page 22

1.4.3. Structural Inductions Page 23

1.4.4. Mutual Inductions Page 26

1.5. The Central Concepts of Automata Theory Page 28

1.5.1. Alphabets Page 28

1.5.2. Strings Page 29

1.5.3. Languages Page 30

1.5.4. Problems Page 31

1.6. Summary of Chapter 1 Page 33

1.7. Gradiance Problems for Chapter 1 Page 35

1.8. References for Chapter 1 Page 36

2. Finite Automata Page 37

2.1. An Informal Picture of Finite Automata Page 38

2.1.1. The Ground Rules Page 38

2.1.2. The Protocol Page 39

2.1.3. Enabling the Automata to Ignore Actions Page 41

2.1.4. The Entire System as an Automaton Page 43

2.1.5. Using the Product Automaton to Validate the Protocol Page 44

2.2. Deterministic Finite Automata Page 45

2.2.1. Definition of a Deterministic Finite Automoton Page 45

2.2.2. How a DFA Processes Strings Page 46

2.2.3. Simpler Notations for DFA's Page 47

2.2.4. Extending the Transition Function to Strings Page 49

2.2.5. The Language of a DFA Page 52

2.2.6. Exercises for Section 2.2 Page 52

2.3. Nondeterministic Finite Automata Page 55

2.3.1. An Informal View of Nondeterministic Finite Automata Page 55

2.3.2. Definition of Nondeterministic Finite Automata Page 57

2.3.3. The Extended Transition Function Page 58

2.3.4. The Language of an NFA Page 59

2.3.5. Equivalence of Deterministic and Nondeterministic Finite Automata Page 60

2.3.6. A Bad Case for the Subset Construction Page 64

2.3.7. Exercises for Section 2.3 Page 65

2.4. An Application: Text Search Page 68

2.4.1. Finding Strings in Text Page 68

2.4.2. Nondeterministic Finite Automata for Text Search Page 69

2.4.3. A DFA to Recognize a Set of Keywords Page 70

2.4.4. Exercises for Section 2.4 Page 71

2.5. Finite Automata With EpsilonTransitions Page 72

2.5.1. Uses of ϵ-Transitions Page 72

2.5.2. The Formal Notation for an ϵ-NFA Page 73

2.5.3. Epsilon-Closures Page 74

2.5.4. Extended Transitions and Languages for ϵ-NFA's Page 75

2.5.5. Eliminationg ϵ-Transitions Page 77

2.5.6. Exercises for Section 2.5 Page 79

2.6. Summary of Chapter 2 Page 80

2.7. Gradiance Problems for Chapter 2 Page 80

2.8. References for Chapter 2 Page 83

3. Regular Expressions and Languages Page 85

3.1. Regular Expressions Page 85

3.1.1. The Operators of Regular Expressions Page 86

3.1.2. Bulding Regular Expressions Page 87

3.1.3. Precedence of Regular-Expression Operators Page 90

3.1.4. Exercises for Section 3.1 Page 91

3.2. Finite Automata and Regular Expressions Page 92

3.2.1. From DFA's to Regular Expressions Page 93

3.2.2. Converting DFA's to Regular Expressions by Eliminating States Page 98

3.2.3. Converting Regular Expressions to Automata Page 102

3.2.4. Exercises for Section 3.2 Page 107

3.3. Applications of Regular Expressions Page 109

3.3.1. Regular Expressions in UNIX Page 109

3.3.2. Lexical Analysis Page 110

3.3.3. Finding Patterns in Text Page 112

3.3.4. Exercises for Section 3.3 Page 114

3.4. Algebraic Laws for Regular Expressions Page 115

3.4.1. Associativity and Commutativity Page 115

3.4.2. Identities and Annihilators Page 116

3.4.3. Distributive Laws Page 116

3.4.4. The Idempotent Laws Page 117

3.4.5. Laws Involving Closures Page 118

3.4.6. Discovering Laws for Regular Expressions Page 118

3.4.7. The Test for a Regular-Expression Algebraic Law Page 120

3.4.8. Exercises for Section 3.4 Page 121

3.5. Summary of Chapter 3 Page 123

3.6. Gradiance Problems for Chapter 3 Page 123

3.7. References for Chapter 3 Page 125

4. Properties of Regular Languages Page 127

4.1. Proving Languages Not to Be Regular Page 128

4.1.1. The Pumping Lemma for Regular Languages Page 128

4.1.2. Applications of the Pumping Lemma Page 129

4.1.3. Exercises for Section 4.1 Page 131

4.2. Closure Properties of Regular Languages Page 133

4.2.1. Closure of Regular Languages Under Boolean Operations Page 133

4.2.2. Reversal Page 139

4.2.3. Homomorphisms Page 140

4.2.4. Inverse Homomorphisms Page 142

4.2.5. Exercises for Section 4.2 Page 147

4.3. Decision Properties of Regular Languages Page 150

4.3.1. Converting Among Representations Page 151

4.3.2. Testing Emptiness of Regular Languages Page 153

4.3.3. Testing Membership in a Regular Language Page 154

4.3.4. Exercises for Section 4.3 Page 155

4.4. Equivalence and Minimization of Automata Page 155

4.4.1. Testing Equivalence of States Page 155

4.4.2. Testing Equivalence of Regular Languages Page 159

4.4.3. Minimization of DFA's Page 160

4.4.4. Why the Minimized DFA Can't Be Beaten Page 163

4.4.5. Exercises for Section 4.4 Page 165

4.5. Summary of Chapter 4 Page 166

4.6. Gradiance Problems for Chapter 4 Page 167

4.7. References for Chapter 4 Page 169

5. Context-Free Grammars and Languages Page 171

5.1. Context-Free Grammars Page 171

5.1.1. An Informal Example Page 172

5.1.2. Definition of Context-Free Grammars Page 173

5.1.3. Derivations Using a Grammar Page 175

5.1.4. Leftmost and Rightmost Derivations Page 177

5.1.5. The Language of a Grammar Page 179

5.1.6. Sentential Forms Page 180

5.1.7. Exercises for Section 5.1 Page 181

5.2. Parse Trees Page 183

5.2.1. Constructing Parse Trees Page 183

5.2.2. The Yield of a Parse Tree Page 185

5.2.3. Inference, Derivations, and Parse Trees Page 185

5.2.4. From Inferences to Trees Page 187

5.2.5. From Trees to Derivations Page 188

5.2.6. From Derivations to Recursive Inferences Page 191

5.2.7. Exercises for sectino 5.2 Page 193

5.3. Applications of Context-Free Grammars Page 193

5.3.1. Parsers Page 194

5.3.2. The YACC Parser-Generator Page 196

5.3.3. Markup Languages Page 197

5.3.4. XML and Document-Type Definitions Page 200

5.3.5. Exercises for Section 5.3 Page 206

5.4. Ambiguity in Grammars and Languages Page 207

5.4.1. Ambiguous Grammars Page 207

5.4.2. Removing Ambiguity From Grammars Page 209

5.4.3. Leftmost Derivations as a Way to Express Ambiguity Page 212

5.4.4. Inherent Ambiguity Page 213

5.4.5. Exercises for Section 5.4 Page 215

5.5. Summary of Chapter 5 Page 216

5.6. Gradiance Problems for Chapter 5 Page 218

5.7. References for Chapter 5 Page 224

6. Pushdown Automata Page 225

6.1. Definition of the Pushdown Automaton Page 225

6.1.1. Informal Introduction Page 225

6.1.2. The Formal Definition of Pushdown Automata Page 227

6.1.3. A Graphical Notation for PDA's Page 229

6.1.4. Instantaneous Descriptions of a PDA Page 230

6.1.5. Exercises for Section 6.1 Page 233

6.2. The Languages of a PDA Page 234

6.2.1. Acceptance by Final State Page 235

6.2.1. Acceptance by Empty Stack Page 236

6.2.1. From Empty Stack to Final State Page 237

6.2.1. From Final State to Empty Stack Page 240

6.2.1. Exercises for Section 6.2 Page 241

6.3. Equivalence of PDA's and CFG's Page 243

6.3.1. From Grammars to Pushdown Automata Page 243

6.3.2. From PDA's to Grammars Page 247

6.3.3. Exercises for Section 6.3 Page 251

6.4. Deterministic Pushdown Automata Page 252

6.4.1. Definition of a Deterministic PDA Page 252

6.4.2. Regular Languages and Deterministic PDA's Page 253

6.4.3. DPDA's and Context-Free Languages Page 254

6.4.4. DPDA's and Ambiguous Grammars Page 255

6.4.5. Exercises for Section 6.4 Page 256

6.5. Summary of Chapter 6 Page 257

6.6. Gradiance Problems for Chapter 6 Page 258

6.7. References for Chapter 6 Page 260

7. Properties of Context-Free Languages Page 261

7.1. Normal Forms for Context-Free Grammars Page 261

7.1.1. Eliminating Useless Symbols Page 263

7.1.2. Computing the Generating and Reachable Symbols Page 264

7.1.3. Eliminating ϵ-Productions Page 265

7.1.4. Eliminating Unit Productions Page 268

7.1.5. Chomsky Normal Form Page 272

7.1.1. Exercises For Section 7.1 Page 275

7.2. The Pumping Lemma for Context-Free Languages Page 179

7.2.1. The Size of Parse Trees Page 280

7.2.2. Statement of the Pumping Lemma Page 280

7.2.3. Applications of the Pumping Lemma for CFL's Page 283

7.2.4. Exercises for Section 7.2 Page 286

7.3. Closure Properties of Context-Free Languages Page 287

7.3.1. Substitutions Page 287

7.3.2. Applications of the Substitution Theorem Page 289

7.3.3. Reversal Page 290

7.3.4. Intersection With a Regular language Page 291

7.3.5. Inverse Homomorphism Page 295

7.3.6. Exercises for Section 7.3 Page 297

7.4. Decision Properties of CFL's Page 299

7.4.1. Complexity of Converting Among CFG's and PDA's Page 299

7.4.2. Running Time of Conversion to Chomsky Normal Form Page 301

7.4.3. Testing Emptiness of CFL's Page 302

7.4.4. Testing Membership in a CFL Page 303

7.4.5. Preview of Undecidable CFL Problems Page 307

7.4.6. Exercises for Section 7.4 Page 307

7.5. Summary of Chapter 7 Page 308

7.6. Gradiance Problems for Chapter 7 Page 309

7.7. References for Chapter 7 Page 314

8. Introduction to Turing Machines Page 315

8.1. Problems That Computers Cannot Solve Page 315

8.1.1. Programs that Print "Hello, World" Page 316

8.1.2. The Hypothetical "Hello, World" Tester Page 318

8.1.3. Reducing One Problem to Another Page 321

8.1.4. Exercises for Section 8.1 Page 324

8.2. The Turing Machine Page 324

8.2.1. The Quest to Decide All Mathematical Questions Page 325

8.2.2. Notation for the Turing Machine Page 326

8.2.3. Instantaneous Descriptions for Turing Machines Page 327

8.2.4. Transition Diagrams for Turing Machines Page 331

8.2.5. The Language of a Turing Machine Page 334

8.2.6. Turing Machines and Halting Page 334

8.2.7. Exercises for Section 8.2 Page 335

8.3. Programming Techniques for Turing Machines Page 337

8.3.1. Storage in the State Page 337

8.3.2. Multiple Tracks Page 339

8.3.3. Subroutines Page 341

8.3.4. Exercises for Section 8.3 Page 343

8.4. Extensions to the Basic Turing Machine Page 343

8.4.1. Multitape Turing Machines Page 344

8.4.2. Equivalence of One-Tape and Multitape TM's Page 345

8.4.3. Running Time and the Many-Tapes-to-One Construction Page 346

8.4.4. Nondeterministic Turing Machines Page 347

8.4.5. Exercises for Section 8.4 Page 349

8.5. Restricted Turing Machines Page 352

8.5.1. Turing Machines with Semi-infinite Tapes Page 352

8.5.2. Multistack Machines Page 355

8.5.3. Counter Machines Page 358

8.5.4. The Power of Counter Machines Page 359

8.5.5. Exercises for Section 8.5 Page 361

8.6. Turing Machines and Computers Page 362

8.6.1. Simulating a Turing Machine by Computer Page 362

8.6.2. Simulating a Computer by a Turing Machine Page 363

8.6.3. Comparing the Running Times of Computers and Turing Machines Page 368

8.7. Summary of Chapter 8 Page 370

8.8. Gradiance Problems for Chapter 8 Page 372

8.9. References for Chapter 8 Page 374

9. Undecidability Page 377

9.1. A Language That Is Not Recursively Enumerable Page 378

9.1.1. Enumerating the Binary Strings Page 379

9.1.2. Codes for Turing Machines Page 379

9.1.3. The Diagonalization Language Page 380

9.1.4. Proof that L[d]XXX Is Not Recursively Enumerable Page 382

9.1.5. Exercises for Section 9.1 Page 382

9.2. An Undecidable Problem That Is RE Page 383

9.2.1. Recursive Languages Page 383

9.2.2. Complements of Recursive and RE languages Page 384

9.2.3. The Universal Language Page 387

9.2.4. Undecidability of the Universal Language Page 389

9.2.5. Exercises for Section 9.2 Page 390

9.3. Undecidable Problems About Turing Machines Page 392

9.3.1. Reductions Page 392

9.3.2. Turing Machines That Accept the Empty Language Page 394

9.3.3. Rice's Theorem and Properties of the RE Languages Page 397

9.3.4. Problems and Turing-Machine Specifications Page 399

9.3.5. Exercises for Section 9.3 Page 400

9.4. Post's Correspondence Problem Page 401

9.4.1. Definition of Post's Correspondence Problem Page 401

9.4.2. The "Modified" PCP Page 404

9.4.3. Completion of the Proof of PCP Undecidability Page 407

9.4.4. Exercises for Section 9.4 Page 412

9.5. Other Undecidable Problems Page 412

9.5.1. Problems About Programs Page 413

9.5.2. Undecidability of Ambiguity for CFG's Page 413

9.5.3. The Complement of a List Language Page 415

9.5.4. Exercises for Section 9.5 Page 418

9.6. Summary of Chapter 9 Page 419

9.7. Gradiance Problems for Chapter 9 Page 420

9.8. References for Chapter 9 Page 422

10. Intractable Problems Page 425

10.1. The Classes P and NP Page 426

10.1.1. Problems Solvable in Polynomial Time Page 426

10.1.2. An Example: Kruskal's Algorithm Page 426

10.1.3. Nondeterministic Polynomial Time Page 431

10.1.4. An NP EXample: The Traveling Salesman Problem Page 431

10.1.5. Polynomial-Time Reductions Page 433

10.1.6. NP-Complete Problems Page 434

10.1.7. Exercises for Section 10.1 Page 435

10.2. An NP-Complete Problem Page 438

10.2.1. The Satisfiability Problem Page 438

10.2.2. Representing SAT Instances Page 439

10.2.3. NP-Completeness of the SAT Problem Page 440

10.2.4. Exercises for Section 10.2 Page 447

10.3. A Restricted Satisfiability Problem Page 447

10.3.1. Normal forms for Boolean Expressions Page 448

10.3.2. Converting Expressions to CNF Page 449

10.3.3. NP-Completeness of CSAT Page 452

10.3.4. NP-Completeness of 3SAT Page 456

10.3.5. Exercises for Section 10.3 Page 458

10.4. Additional NP-Complete Problems Page 458

10.4.1. Describing NP-complete Problems Page 459

10.4.2. The Problem of Independent Sets Page 459

10.4.3. The Node-Cover Problem Page 463

10.4.4. The Directed Hamilton-Circuit Problem Page 465

10.4.5. Undirected Hamilton Circuits and the TSP Page 471

10.4.6. Summary of NP-Complete Problems Page 473

10.4.7. Exercises for Section 10.4 Page 473

10.5. Summary of Chapter 10 Page 477

10.6. Gradiance Problems for Chapter 10 Page 478

10.7. References for Chapter 10 Page 481

11. Additional Classes of Problems Page 483

11.1. Complements of Languages in NP Page 484

11.1.1. The Class of Languages Co-NP Page 484

11.1.2. NP-Complete Preblems and Co-NP Page 485

11.1.3. Exercises for Section 11.1 Page 486

11.2. Problems Solvable in Polynomial Space Page 487

11.2.1. Polynomial-Space Turing Machines Page 487

11.2.2. Relationship of PS and NPS to Previously Defined Classes Page 488

11.2.3. Deterministic and Nondeterministic Polynomial Space Page 490

11.3. A Problem That Is Complete for PS Page 492

11.3.1. PS-Completeness Page 492

11.3.2. Quantified Boolean Formulas Page 493

11.3.3. Evaluating Quantified Boolean Formulas Page 494

11.3.4. PS-Completeness of the QBF Problem Page 496

11.3.5. Exercises for Section 11.3 Page 501

11.4. Language Classes Based on Randomization Page 501

11.4.1. Quicksort: an Example of a Randomized Algorithm Page 502

11.4.2. A Turing-Machine Model using Randomization Page 503

11.4.3. The Language of a Randomized Turing Machine Page 504

11.4.4. The Class RP Page 508

11.4.5. Recognizing Languages in RP Page 508

11.4.6. The Class ZPP Page 509

11.4.7. Relationship Between RP and ZPP Page 510

11.4.8. Relationships to the Classes P and NP Page 511

11.5. The Complexity of Primality Testing Page 512

11.5.1. The Importance of Testing Primality Page 512

11.5.2. Introduction to Modular Arithmetic Page 514

11.5.3. The Complexity of Modular-Arithmetic Computations Page 516

11.5.4. Random-Polynomial Primality Testing Page 517

11.5.5. Nondeterministic Primality Tests Page 518

11.5.6. Exercises for Section 11.5 Page 521

11.6. Summary of Chapter 11 Page 522

11.7. Gradiance Problems for Chapter 11 Page 523

11.8. References for Chapter 11 Page 524

Index Page 527

Edition Notes

Classifications

Library of Congress: QA267 .H56 2006, QA267 .H56 2007, QA267.H56 2006

Contributors

Author: Rajeev Motwani
Author: Jeffrey D. Ullman

The Physical Object

Format: Hardcover
Pagination: xvii, 535p
Number of pages: 535

ID Numbers

Open Library: OL24357442M
ISBN 10: 0321455363
LCCN: 2006014263
OCLC/WorldCat: 69013079

Community Reviews (0)

Feedback?

No community reviews have been submitted for this work.

Lists

See All

CompSci from Douglas Latimer

CS from Tuxeye
Computer science Texts from bhajjaka

History

Created September 12, 2010
18 revisions

Download catalog record: RDF / JSON / OPDS | Wikipedia citation

February 25, 2024	Edited by OL-00	Edited without comment.
December 19, 2023	Edited by ImportBot	import existing book
October 20, 2023	Edited by Drini	Fix TOC
March 8, 2023	Edited by MARC Bot	import existing book
September 12, 2010	Created by C. A. Russell	Added new book.

Introduction to automata theory, languages, and computation

by John E. Hopcroft, Jeffrey D. Ullman, and Rajeev Motwani