Elements of theory of computation /
Harry R. Lewis
Elements of theory of computation / - 1 - Estados Unidos Prentice hall 1981 - 459 15cm de ancho X 23cm de largo - Serie .
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.
0-13-273417-6
LCC
Elements of theory of computation / - 1 - Estados Unidos Prentice hall 1981 - 459 15cm de ancho X 23cm de largo - Serie .
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.
0-13-273417-6
LCC
