Theory of Computation

Derick Wood

First Edition---Contents

Preface...iii

Course Outlines...xvii

PART I--INTRODUCTION...1

Chapter 0--PRELIMINARIES

  • 0.1--Sequences, Sets, and Tuples...3
  • 0.2--Directed Graphs...9
  • 0.3--Functions, Relations, and Closure...17
  • 0.4--Cardinality, Countability, and Enumerability...27
  • 0.5--Proof Methods and Techniques...28
  • 0.6--Additional Remarks...38
  • 0.6.1--Summary...38
  • 0.6.2--Further Reading...38
  • Exercises...38
  • Programming Projects...49

    • Chapter 1--LANGUAGES AND COMPUTATION

  • 1.1--Programming Problems and Computation...50
  • 1.2--Alphabets, Words, and Languages...63
  • 1.3--Languages, Problems, and Computation...77
  • 1.4--Additional Remarks...80
  • 1.4.1--Summary...80
  • 1.4.2--History...80
  • 1.5--Springboard...81
  • Exercises...86
  • Programming Projects...90

    • PART II--MODELS...93

    Chapter 2--FINITE AUTOMATA

  • 2.1--States, State Diagrams, and Transitions...95
  • 2.2--Deterministic Finite Automata...98
  • 2.3--Nondeterministic Finite Automata...111
  • 2.4--Minimization and Simplification...127
  • 2.5--DFAs and Tries...133
  • 2.6--Lambda-FAs and Lazy FAs...135
  • 2.7--Additional Remarks...142
  • 2.7.1--Summary...142
  • 2.7.2--History...143
  • 2.8--Springboard...143
  • Exercises...147
  • Programming Projects...153

    • Chapter 3--REGULAR EXPRESSIONS

  • 3.1--Motivation and Definition...155
  • 3.2--Regular Expressions into Finite Automata...161
  • 3.3--Extended Finite Automata into Regular Expressions...166
  • 3.4--Extended Regular Expressions...175
  • 3.5--Additional Remarks...179
  • 3.5.1--Summary...179
  • 3.5.2--History...179
  • 3.6--Springboard...180
  • Exercises...182
  • Programming Projects...185

    • Chapter 4--CONTEXT-FREE GRAMMARS

  • 4.1--Basics of Context-Free Grammars...187
  • 4.2--Simplifications...211
  • 4.3--Linear and Regular Grammars...229
  • 4.4--Extended Context-Free Grammars...232
  • 4.5--Additional Remarks...236
  • 4.5.1--Summary...236
  • 4.5.2--History...237
  • 4.6--Springboard...237
  • Exercises...240
  • Programming Projects...246

    • Chapter 5--PUSHDOWN AUTOMATA

  • 5.1--Deterministic Pushdown Automata...248
  • 5.2--Nondeterministic Pushdown Automata...259
  • 5.3*--Counter Automata...270
  • 5.4*--Two-Way Deterministic Pushdown Automata...271
  • 5.5--Additional Remarks...273
  • 5.5.1--Summary...273
  • 5.5.2--History...274
  • 5.6--Springboard...274
  • Exercises...276
  • Programming Projects...279

    • Chapter 6--TURING MACHINES

  • 6.1--The Turing Machine...280
  • 6.2--Turing Machine Programming...295
  • 6.3*--Simplifications...301
  • 6.4--Extensions...311
  • 6.5--Universal Turing Machines...320
  • 6.6--Resource-Bounded Turing Machines...326
  • 6.7--Additional Remarks...331
  • 6.7.1--Summary...331
  • 6.7.2--History...331
  • 6.8--Springboard...331
  • Exercises...334
  • Programming Projects...337

    • Chapter 7--FUNCTIONS, RELATIONS, AND TRANSLATIONS

  • 7.1--Introduction...338
  • 7.2--Finite Transducers...339
  • 7.3--Translation Grammars...348
  • 7.4--Pushdown Transducers...352
  • 7.5--Turing Machines and Computable Functions...355
  • 7.6--Recursive Functions...359
  • 7.7--Additional Remarks...364
  • 7.7.1--Summary...364
  • 7.7.2--History...364
  • 7.8--Springboard...364
  • Exercises...366
  • Programming Projects...368

    • PART III--PROPERTIES...371

    Chapter 8--FAMILY RELATIONSHIPS

  • 8.1--Finite, Regular, and Context-Free Languages...373
  • 8.2--Context-Free and Tractable Languages...382
  • 8.3*--Tractable and Recursive Languages...397
  • 8.4--Recursive and DTM Languages...403
  • 8.5--Additional Remarks...406
  • 8.5.1--Summary...406
  • 8.5.2--History...406
  • 8.6--Springboard...407
  • Exercises...408

    • Chapter 9--CLOSURE PROPERTIES

  • 9.1--Boolean and Reversal Operations...412
  • 9.2--Mappings...420
  • 9.3--Catenation, Quotient, and Star...434
  • 9.4--Composition...435
  • 9.5--Cylinders, Cones, and AFLs...438
  • 9.6--Additional Remarks...440
  • 9.6.1--Summary...440
  • 9.6.2--History...440
  • 9.7--Springboard...441
  • Exercises...441

    • Chapter 10--DECISION PROBLEMS

  • 10.1--Decidability and Membership...446
  • 10.2--Emptiness and Finiteness...450
  • 10.3--Containment, Equivalence, and Intersection...454
  • 10.4--Context-Free Ambiguity...462
  • 10.5--Additional Remarks...462
  • 10.5.1--Summary...462
  • 10.5.2--History...462
  • 10.6--Springboard...463
  • Exercises...464

    • PART IV--ONWARD...469

    Chapter 11--FURTHER TOPICS

  • 11.1--NP-Complete Problems...472
  • 11.2--Rewriting Systems and Church's Thesis...497
  • 11.3--Parsing...504
  • 11.4--Additional Remarks...523
  • 11.4.1--Summary...523
  • 11.4.2--History...523
  • 11.5--Springboard...524
  • Exercises...526

    • BIBLIOGRAPHY...531

    INDEX...547

    http://www.cs.ust.hk/~dwood/.toc
    dwood@cs.ust.hk
    Computer Science Department
    The Hong Kong University of Science and Technology
    Clear Water Bay, Kowloon
    HONG KONG