Theory of Computation---Contents

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.1.1--Sets and Their Specification...3

0.1.2--Set Operations...6

0.1.3--Multisets...8

0.1.4--Sequences...8

0.1.5--Tuples...9

0.2--Directed Graphs...9

0.2.1--Digraphs...10

0.2.2--Multiset Digraphs and Trees...14

0.3--Functions, Relations, and Closure...17

0.3.1 --Functions...17

0.3.2--Big-O Notation...19

0.3.3--Relations...20

0.3.4--Closure...25

0.4--Cardinality, Countability, and Enumerability...27

0.5--Proof Methods and Techniques...28

0.5.1--Direct Proof...29

0.5.2--Proof by Contradiction...30

0.5.3--Proof by Induction...31

0.5.4--The Pigeonhole Principle...34

0.5.5--Counting...35

0.5.6--Diagonalization...36

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.2.1--Alphabets and Words...64

1.2.2--Languages and Operations...68

1.2.3--Defining Languages...71

1.2.4--Definition Summaries...76

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

1.5.1--The Lambda Calculus...81

1.5.2--Markov Algorithms...81

1.5.3--Post Systems and Production Systems...82

1.5.4--Recursive Functions...83

1.5.5--Formal Semantics...84

1.5.6--Program Correctness...85

1.5.7--Program Construction...86

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.6.1--Lambda-FAs and Lambda-Transitions...135

2.6.2--Lazy Finite Automata...140

2.7--Additional Remarks...142

2.7.1--Summary...142

2.7.2--History...143

2.8--Springboard...143

2.8.1--The Syntactic Monoid...143

2.8.2--Life and Cellular Automata...144

2.8.3--Communication Protocols...144

2.8.4--Security...144

2.8.5--Tree Automata...145

2.8.6--Avoiding Spaghetti Programming...145

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

3.6.1--A Differential Calculus...180

3.6.2--Descriptional Complexity...180

3.6.3--VLSI...181

3.6.4--Path Expressions...181

Exercises...182

Programming Projects...185

Chapter 4--CONTEXT-FREE GRAMMARS

4.1--Basics of Context-Free Grammars...187

4.2--Simplifications...211

4.2.1--Redundant Symbols...212

4.2.2--Empty Productions...215

4.2.3--Unit Productions...220

4.2.4--Binary Form and Chomsky Normal Form...221

4.2.5--Greibach Normal Form and Two-Standard Normal Form...224

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

4.6.1--Recognition and Parsing...237

4.6.2--Ambiguity...238

4.6.3--W-grammars...238

4.6.4--Simplifications and Efficiency...239

4.6.5--Context-Free Expressions...239

4.6.6--E0L Grammars and Languages...239

4.6.7--ALGOL-Like Languages...240

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

5.6.1--Data Structure Automata...274

5.6.2--Preset Pushdown Automata...274

5.6.3--Multihead and Multipushdown Automata...274

5.6.4--Finite-Buffer PDAs and Lazy PDAs...274

5.6.5--Small PDAs...275

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.4.1--Two-Way Infinite Tape Turing Machines...312

6.4.2--Nondeterministic Turing Machines...316

6.4.3--Multihead Turing Machines...318

6.4.4--Multitape Turing Machines...320

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

6.8.1--The Busy Beaver Game...331

6.8.2--The Turing Micros...332

6.8.3--Computable Functions...333

6.8.4--NP-Completeness...333

6.8.5--Simulation Efficiency...333

6.8.6--Recursively Enumerable Languages...334

6.8.7--Context-Sensitive Languages...334

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

7.8.1--Lexical Analysis...364

7.8.2--Syntax-Directed Translations...364

7.8.3--File Compaction...365

7.8.4--Translation Expressions...365

7.8.5--String Similarity...365

7.8.6--Recursive Function Theory...365

Exercises...366

Programming Projects...368

PART III--PROPERTIES...371

Chapter 8--FAMILY RELATIONSHIPS

8.1--Finite, Regular, and Context-Free Languages...373

8.1.1--Introduction...373

8.1.2--Regular Languages...375

8.1.3*--Unary Regular Languages...379

8.2--Context-Free and Tractable Languages...382

8.2.1--Deterministic Context-Free Languages...382

8.2.2*--Tractable Languages...383

8.2.3--Context-Free Pumping Lemma...387

8.2.4*--Parikh's Theorem...394

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

8.6.1--Hierarchy Results...407

8.6.2--Pumping Lemmas...407

8.6.3--Nonlanguages and Closure Properties...408

Exercises...408

Chapter 9--CLOSURE PROPERTIES

9.1--Boolean and Reversal Operations...412

9.2--Mappings...420

9.2.1--Morphism and Substitution...420

9.2.2*--Inverse Morphism and Finite Transduction...429

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

9.7.1--Closure Properties...441

9.7.2--Cones...441

Exercises...441

Chapter 10--DECISION PROBLEMS

10.1--Decidability and Membership...446

10.1.1--Introduction...446

10.1.2--Finite Automata...447

10.1.3--Context-Free Grammars...447

10.1.4--Deterministic Turing Machines...448

10.2--Emptiness and Finiteness...450

10.2.1--Finite Automata...450

10.2.2--Context-Free Grammars...451

10.2.3--Deterministic Turing Machines...452

10.3--Containment, Equivalence, and Intersection...454

10.3.1--Finite Automata...454

10.3.2--Context-Free Grammars...455

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

10.6.1--Post's Correspondence Problem...463

Exercises...464

PART IV--ONWARD...469

Chapter 11--FURTHER TOPICS

11.1--NP-Complete Problems...472

11.1.1--The Ordering...472

11.1.2--An NP-Complete Problem...475

11.1.3--Satisfiability...476

11.1.4--Traveling Salesman...481

11.1.5--Subset Sum...488

11.1.6--Hierarchical Grammars...492

11.2--Rewriting Systems and Church's Thesis...497

11.2.1--Phrase Structure Grammars...497

11.2.2--Interactive Lindenmayer Grammars...500

11.3--Parsing...504

11.3.1--General CFG Parsing...504

11.3.2--Deterministic Top-Down Parsing...507

11.3.3--Deterministic Bottom-Up Parsing...515

11.4--Additional Remarks...523

11.4.1--Summary...523

11.4.2--History...523

11.5--Springboard...524

11.5.1--Dealing with NP-Completeness...524

11.5.2--LALR Grammars...525

11.5.3--Other Kinds of Completeness...525

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