An edition of Theory of computation (1987)

Theory of computation

by

  • ★★★★★ 5.0 (2 ratings)
  • 7 Want to read
  • 2 Currently reading
  • 1 Have read
Cover of: Theory of computation by Derick Wood, Derick Wood
Preview Only

My Reading Lists:

Create a new list
Notes
  • ★★★★★ 5.0 (2 ratings)
  • 7 Want to read
  • 2 Currently reading
  • 1 Have read
Notes

Check nearby libraries

Buy this book

Last edited by Drini
September 14, 2025 | History
Edit
An edition of Theory of computation (1987)

Theory of computation

by

  • ★★★★★ 5.0 (2 ratings)
  • 7 Want to read
  • 2 Currently reading
  • 1 Have read

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

Publish Date
Publisher
Wiley
Language
English
Pages
558

Check nearby libraries

Buy this book

Previews available in: English

Subjects

Computational complexity, Computer science, Machine theory, Mathematics, Computers
Edition Availability
Cover of: Theory of computation
Theory of computation
1987, Harper & Row
in English
Cover of: Theory of computation
Theory of computation
1987, Wiley
in English
Cover of: Theory of computation
Theory of computation
1987, Wiley
in English

Add another edition?

Book Details

Table of Contents

Preface
Page xiii
Course Outlines
Page xvii
Part I. Introduction
Page 1
Chapter 0. Preliminaries
0.1. Sequences, Sets, and Tuples
Page 3
0.1.1. Sets and Their Specification
Page 3
0.1.2. Set Operations
Page 6
0.1.3. Multisets
Page 8
0.1.4. Sequences
Page 8
0.1.5. Tuples
Page 9
0.2. Directed Graphs
Page 9
0.2.1. Digraphs
Page 10
0.2.2. Multiset Digraphs and Trees
Page 14
0.3. Functions, Relations, and Closure
Page 17
0.3.1. Functions
Page 17
0.3.2. Big-O Notation
Page 19
0.3.3. Relations
Page 20
0.3.4. Closure
Page 25
0.4. Cardinality, Countability, and Enumerability
Page 27
0.5. Proof Methods and Techniques
Page 28
0.5.1. Direct Proof
Page 29
0.5.2. Proof by Contradiction
Page 30
0.5.3. Proof by Induction
Page 31
0.5.4. The Pigeonhole Principle
Page 34
0.5.5. Counting
Page 35
0.5.6. Diagonalization
Page 36
0.6. Additional Remarks
Page 38
0.6.1. Summary
Page 38
0.6.2. Further Reading
Page 38
Exercises
Page 38
Programming Projects
Page 49
Chapter 1. Languages and Computation
1.1. Programming Problems and Computation
Page 50
1.2. Alphabets, Words, and Languages
Page 63
1.2.1. Alphabets and Words
Page 64
1.2.2. Languages and Operations
Page 68
1.2.3. Defining Languages
Page 71
1.2.4. Definition Summaries
Page 76
1.3. Languages, Problems, and Computation
Page 77
1.4. Additional Remarks
Page 80
1.4.1. Summary
Page 80
1.4.2. History
Page 80
1.5. Springboard
Page 81
1.5.1. The 2-Calculus
Page 81
1.5.2. Markov Algorithms
Page 81
1.5.3. Post Systems and Production Systems
Page 82
1.5.4. Recursive Functions
Page 83
1.5.5. Formal Semantics
Page 84
1.5.6. Program Correctness
Page 85
1.5.7. Program Construction
Page 86
Exercises
Page 86
Programming Projects
Page 90
Part II. Models
Page 93
Chapter 2. Finite Automata
2.1. States, State Diagrams, and Transitions
Page 95
2.2. Deterministic Finite Automata
Page 98
2.3. Nondeterministic Finite Automata
Page 111
2.4. Minimization and Simplification
Page 127
2.5. DFAs and Tries
Page 133
2.6. λ-FAs and Lazy FAs
Page 135
2.6.1. 2-FAs and 2-Transitions
Page 135
2.6.2. Lazy Finite Automata
Page 140
2.7. Additional Remarks
Page 142
2.7.1. Summary
Page 142
2.7.2. History
Page 143
2.8. Springboard
Page 143
2.8.1. The Syntactic Monoid
Page 143
2.8.2. Life and Cellular Automata
Page 144
2.8.3. Communication Protocols
Page 144
2.8.4. Security
Page 144
2.8.5. Tree Automata
Page 145
2.8.6. Avoiding Spaghetti Programming
Page 145
Exercises
Page 147
Programming Projects
Page 153
Chapter 3. Regular Expressions
Page 155
3.1. Motivation and Definition
Page 155
3.2. Regular Expressions into Finite Automata
Page 161
3.3. Extended Finite Automata into Regular Expressions
Page 166
3.4. Extended Regular Expressions
Page 175
3.5. Additional Remarks
Page 179
3.5.1. Summary
Page 179
3.5.2. History
Page 179
3.6. Springboard
Page 180
3.6.1. A Differential Calculus
Page 180
3.6.2. Descriptional Complexity
Page 180
3.6.3. VLSI
Page 181
3.6.4. Path Expressions
Page 181
Exercises
Page 182
Programming Projects
Page 185
Chapter 4. Context-Free Grammars
Page 187
4.1. Basics of Context-Free Grammars
Page 187
4.2. Simplifications
Page 211
4.2.1. Redundant Symbols
Page 212
4.2.2. Empty Productions
Page 215
4.2.3. Unit Productions
Page 220
4.2.4. Binary Form and Chomsky Normal Form
Page 221
4.2.5. Greibach Normal Form and Two-Standard Normal Form
Page 224
4.3. Linear and Regular Grammars
Page 229
4.4. Extended Context-Free Grammars
Page 232
4.5. Additional Remarks
Page 236
4.5.1. Summary
Page 236
4.5.2. History
Page 237
4.6. Springboard
Page 237
4.6.1. Recognition and Parsing
Page 237
4.6.2. Ambiguity
Page 238
4.6.3. W-grammars
Page 238
4.6.4. Simplifications and Efficiency
Page 239
4.6.5. Context-Free Expressions
Page 239
4.6.6. EOL Grammars and Languages
Page 239
4.6.7. ALGOL-Like Languages
Page 240
Exercises
Page 240
Programming Projects
Page 246
Chapter 5. Pushdown Automata
Page 248
5.1. Deterministic Pushdown Automata
Page 248
5.2. Nondeterministic Pushdown Automata
Page 259
5.3*. Counter Automata *
Page 270
5.4*. Two-Way Deterministic Pushdown Automata *
Page 271
5.5. Additional Remarks
Page 273
5.5.1. Summary
Page 273
5.5.2. History
Page 274
5.6. Springboard
Page 274
5.6.1. Data Structure Automata
Page 274
5.6.2. Preset Pushdown Automata
Page 274
5.6.3. Multihead and Multipushdown Automata
Page 274
5.6.4. Finite-Buffer PDAs and Lazy PDAs
Page 274
5.6.5. Small PDAs
Page 275
Exercises
Page 276
Programming Projects
Page 279
Chapter 6. Turing Machines
Page 280
6.1. The Turing Machine
Page 280
6.2. Turing Machine Programming
Page 295
6.3*. Simplifications *
Page 301
6.4. Extensions
Page 311
6.4.1. Two-Way Infinite Tape Turing Machines
Page 312
6.4.2. Nondeterministic Turing Machines
Page 316
6.4.3. Multihead Turing Machines
Page 318
6.4.4. Multitape Turing Machines
Page 320
6.5. Universal Turing Machines
Page 320
6.6. Resource-Bounded Turing Machines
Page 326
6.7. Additional Remarks
Page 331
6.7.1. Summary
Page 331
6.7.2. History
Page 331
6.8. Springboard
Page 331
6.8.1. The Busy Beaver Game
Page 331
6.8.2. The Turing Micros
Page 332
6.8.3. Computable Functions
Page 333
6.8.4. NP-Completeness
Page 333
6.8.5. Simulation Efficiency
Page 333
6.8.6. Recursively Enumerable Languages
Page 334
6.8.7. Context-Sensitive Languages
Page 334
Exercises
Page 334
Programming Projects
Page 337
Chapter 7. Functions, Relations, and Translations
Page 338
7.1. Introduction
Page 338
7.2. Finite Transducers
Page 339
7.3. Translation Grammars
Page 348
7.4. Pushdown Transducers
Page 352
7.5. Turing Machines and Computable Functions
Page 355
7.6. Recursive Functions
Page 359
7.7. Additional Remarks
Page 364
7.7.1. Summary
Page 364
7.7.2. History
Page 364
7.8. Springboard
Page 364
7.8.1. Lexical Analysis
Page 364
7.8.2. Syntax-Directed Translations
Page 364
7.8.3. File Compaction
Page 365
7.8.4. Translation Expressions
Page 365
7.8.5. String Similarity
Page 365
7.8.6. Recursive Function Theory
Page 365
Exercises
Page 366
Programming Projects
Page 368
Part III. Properties
Page 371
Chapter 8. Family Relationships
Page 373
8.1. Finite, Regular, and Context-Free Languages
Page 373
8.1.1. Introduction
Page 373
8.1.2. Regular Languages
Page 375
8.1.3*. Unary Regular Languages *
Page 379
8.2. Context-Free and Tractable Languages
Page 382
8.2.1. Deterministic Context-Free Languages
Page 382
8.2.2*. Tractable Languages *
Page 383
8.2.3. Context-Free Pumping Lemma
Page 387
8.2.4*. Parikh's Theorem *
Page 394
8.3*. Tractable and Recursive Languages *
Page 397
8.4. Recursive and DTM Languages
Page 403
8.5. Additional Remarks
Page 406
8.5.1. Summary
Page 406
8.5.2. History
Page 406
8.6. Springboard
Page 407
8.6.1. Hierarchy Results
Page 407
8.6.2. Pumping Lemmas
Page 407
8.6.3. Nonlanguages and Closure Properties
Page 408
Exercises
Page 408
Chapter 9. Closure Properties
Page 412
9.1. Boolean and Reversal Operations
Page 412
9.2. Mappings
Page 420
9.2.1. Morphism and Substitution
Page 420
9.2.2*. Inverse Morphism and Finite Transduction *
Page 429
9.3. Catenation, Quotient, and Star
Page 434
9.4. Composition
Page 435
9.5. Cylinders, Cones, and AFLs
Page 438
9.6. Additional Remarks
Page 440
9.6.1. Summary
Page 440
9.6.2. History
Page 440
9.7. Springboard
Page 441
9.7.1. Closure Properties
Page 441
9.7.2. Cones
Page 441
Exercises
Page 441
Chapter 10. Decision Problems
Page 446
10.1. Decidability and Membership
Page 446
10.1.1. Introduction
Page 446
10.1.2. Finite Automata
Page 447
10.1.3. Context-Free Grammars
Page 447
10.1.4. Deterministic Turing Machines
Page 448
10.2. Emptiness and Finiteness
Page 450
10.2.1. Finite Automata
Page 450
10.2.2. Context-Free Grammars
Page 451
10.2.3. Deterministic Turing Machines
Page 452
10.3. Containment, Equivalence, and Intersection
Page 454
10.3.1. Finite Automata
Page 454
10.3.2. Context-Free Grammars
Page 455
10.4. Context-Free Ambiguity
Page 462
10.5. Additional Remarks
Page 462
10.5.1. Summary
Page 462
10.5.2. History
Page 462
10.6. Springboard
Page 463
10.6.1. Post's Correspondence Problem
Page 463
Exercises
Page 464
Part IV. Onward
Page 469
Chapter 11. Further Topics
11.1. NP-Complete Problems
Page 472
11.1.1. The Ordering ∝
Page 472
11.1.2. An NP-Complete Problem
Page 475
11.1.3. Satisfiability
Page 476
11.1.4. Traveling Salesman
Page 481
11.1.5. Subset Sum
Page 488
11.1.6. Hierarchical Grammars
Page 492
11.2. Rewriting Systems and Church's Thesis
Page 497
11.2.1. Phrase Structure Grammars
Page 497
11.2.2. Interactive Lindenmayer Grammars
Page 500
11.3. Parsing
Page 504
11.3.1. General CFG Parsing
Page 504
11.3.2. Deterministic Top-Down Parsing
Page 507
11.3.3. Deterministic Bottom-Up Parsing
Page 515
11.4. Additional Remarks
Page 523
11.4.1. Summary
Page 523
11.4.2. History
Page 523
11.5. Springboard
Page 524
11.5.1. Dealing with NP-Completeness
Page 524
11.5.2. LALR Grammars
Page 525
11.5.3. Other Kinds of Completeness
Page 525
Exercises
Page 526
Bibliography
Page 531
Index
Page 547

Edition Notes

Bibliogr.

1

Published in
New York, NY

Classifications

Library of Congress
QA'267'W66'1987b, QA267 .W66 1987b

The Physical Object

Pagination
xviii, 558 p. :
Number of pages
558

Edition Identifiers

Open Library
OL20650900M
ISBN 10
0471603511
LibraryThing
257623

Work Identifiers

Work ID
OL4106911W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
September 14, 2025 Edited by Drini Add TOC from Tocky
April 12, 2023 Edited by ImportBot import existing book
December 9, 2022 Edited by ImportBot import existing book
October 18, 2022 Edited by ImportBot import existing book
October 29, 2008 Created by ImportBot Imported from The Laurentian Library MARC record