Elements of theory of computation /

PREFACE

Chapter 1 SETS, RELATIONS, AND LANGUAGES

1.1 "If-Then" and its Relatives 1

1.2 Sets 5

1.3 Relations and Functions 8

1.4 Special Types of Binary Relations

12

1.5 Closures 18

1.6 Finite and Infinite Sets 21

1.7 Three Fundamental Proof Techniques

23

1.8 Alphabets and Languages 29

1.9 Finite Representation of Languages

33

Problems 39

References 47
CONTENTS

Chapter 2 FINITE AUTOMATA

2.1 Deterministic Finite Automata 49

2.2 Nondeterministic Finite Automate 54

2.3 Equivalence of Deterministic and Nondatsministic Finite Automata 59

2.4 Properties of the Languages Accepted by Finito Automata 64

2.5 Finite Automata and Regular Expressions 69

2.6 Proofs that Languages Are and Are Not Regular 73

Problems 76

References 53

Chapter 3 CONTEXT-FREE LANGUAGES

31 Context-Free Grammars 95

3.2 Regular Languages and Context-Fres Languages 102

3.3 Pushdown Automata 105

3.4 Pushdown Automata and Context-Free Grammars 110

3.5 Properties of Context-Free Languages 119

3.5.1 Closure Properties 120

3.5.2 Periodicity Properties 122

3.5.3 Algorithmic Properties 131

3.6 Determinism and Parsing 134

3.6.1 Deterministic Pushdown Automata and Context-Free

Languages 135

3.6.2 Top-Down Parsing 138

3.6.3 Bottom-Up Parsing 146

Problems 153

References 164

CONTENTS

Chapter 4 TURING MACHINES

4.1 The Dafinition of a Turing Machine 168

4.2 Computing with Turing Machines 175

4.3 Combining Turing Machines 180

Some Examples of More Powerful Turing Machines 187

4.5 Extensions of the Turing Mechine 192

46 Nondstorministic Turing Machines 204

Problems 211

References 221

Chapter 5 CHURCH'S THESIS

5.1 Church's Thesis 222

5.2 Grammars 224

5.3 The Primitive Recursive Functions 232

54 Gödelization 242

5.5 The -Recursive Functions 248

5.6 Turing-Computability of the -Recursive Functions 252

5.7 Universal Turing Machines 258

Problems 262

References 271

Chapter 6 UNCOMPUTABILITY

6.1 The Halting Problem 272

6.2 Turing-Enumorability, Turing-Acceptability. and Turing-Decidability

PREFACE

This book is an introduction, on the undergraduate level, to the classi-cal and contemporary theory of computation. The topics covered are, in a few words, the theory of automata and formal languages, computability by Turing machines and recursive functions, uncomputability, computational complexity, and mathematical logic. The treatment is mathematical but the viewpoint is that of computer science; thus the chapter on context-free languages includes a discussion of parsing, and the chapters on logic establish the soundness and completeness of resolution theorem-proving.

In the undergraduate curriculum, exposure to this subject tends to come late, if at all, and collaterally with courses on the design and analysis of algorithms. It is our view that computer science students should be exposed to this material earlier as sophomores or juniors-both because of the deeper insights it yields on specific topics in computer science, and because it serves to establish essential mathematical paradigms. But we have found teaching a rigorous undergraduate course on the subject a difficult under-taking because of the mathematical maturity assumed by the more advanced textbooks. Our goal in writing this book has been to make the essentials of the subject accessible to a broad undergraduate audience in a way that is mathematically sound but presupposes no special mathematical experience.

The whole book represents about a year's worth of coursework. We have each taught a one-term course covering much of the material in Chap-ters I through 6, omitting on various occasions and in various combinations the sections on parsing, on recursive functions, and on particular unsolvable decision problems. Other selections are also possible; for example, a course xiv

PREFACE

emphasizing computability and the foundations of mechanical logic might skip quickly over Chapters 1 through 3 and concentrate on Chapters 4, 6, 8, and 9. However it is used, our fervent hope is that the book will contribute to the intellectual development of the next generation of computer scientists by introducing them at an early stage of their education to crisp and method-ical thinking about computational problems.

We take this opportunity to thank all from whom we have learned, both teachers and students. Specific thanks go to Larry Denenberg and Aaron Temin for their proofreading of early drafts, and to Michael Kahl and Oded Shmueli for their assistance and advice as teaching assistants. In the spring of 1980 Albert Meyer taught a course at M.I.T. from a draft of this book, and we thank him warmly for his criticisms and corrections. Of course, the blame for any remaining errors rests with us alone. Renate D'Arcangelo typed and illustrated the manuscript with her characteristic but extraordinary perfec-tionism and rapidity.

Ingeniería en Tecnologías de la Información y Comunicación