This textbook provides undergraduate students with an introduction to the basic theoretical models of computability, and develops some of the model's rich and varied structure. The first part of the book is devoted to finite automata and their properties. Pushdown automata provide a broader class of models and enable the analysis of context-free languages. In the remaining chapters, Turing machines are introduced and the book culminates in analyses of effective computability, decidability, and Gödel's incompleteness theorems. Students who already have some experience with elementary discrete mathematics will find this a well-paced first course, and a number of supplementary chapters introduce more advanced concepts.
Author(s): Dexter C. Kozen
Series: Undergraduate Texts in Computer Science
Publisher: Springer
Year: 1977
Language: English
Pages: 399
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity
Front Matter....Pages i-xiii
Front Matter....Pages 1-1
Course Roadmap and Historical Perspective....Pages 3-6
Strings and Sets....Pages 7-13
Finite Automata and Regular Sets....Pages 14-18
More on Regular Sets....Pages 19-24
Nondeterministic Finite Automata....Pages 25-31
The Subset Construction....Pages 32-39
Pattern Matching....Pages 40-43
Pattern Matching and Regular Expressions....Pages 44-48
Regular Expressions and Finite Automata....Pages 49-54
Kleene Algebra and Regular Expressions....Pages 55-60
Homomorphisms....Pages 61-66
Limitations of Finite Automata....Pages 67-71
Using the Pumping Lemma....Pages 72-76
DFA State Minimization....Pages 77-83
A Minimization Algorithm....Pages 84-88
Myhill—Nerode Relations....Pages 89-94
The Myhill—Nerode Theorem....Pages 95-99
Collapsing Nondeterministic Automata....Pages 100-107
Automata on Terms....Pages 108-113
The Myhill—Nerode Theorem for Term Automata....Pages 114-118
Front Matter....Pages 1-1
Two-Way Finite Automata....Pages 119-123
2DFAs and Regular Sets....Pages 124-128
Context-Free Grammars and Languages....Pages 129-134
Balanced Parentheses....Pages 135-139
Normal Forms....Pages 140-147
The Pumping Lemma for CFLs....Pages 148-156
Pushdown Automata....Pages 157-163
Final State Versus Empty Stack....Pages 164-166
PDAs and CFGs....Pages 167-171
Simulating NPDAs by CFGs....Pages 172-175
Deterministic Pushdown Automata....Pages 176-180
Parsing....Pages 181-190
The Cocke—Kasami—Younger Algorithm....Pages 191-197
The Chomsky—Schützenberger Theorem....Pages 198-200
Parikh’s Theorem....Pages 201-205
Turing Machines and Effective Computability....Pages 206-214
More on Turing Machines....Pages 215-220
Equivalent Models....Pages 221-225
Universal Machines and Diagonalization....Pages 228-233
Decidable and Undecidable Problems....Pages 235-238
Front Matter....Pages 1-1
Reduction....Pages 239-244
Rice’s Theorem....Pages 245-248
Undecidable Problems About CFLs....Pages 249-255
Other Formalisms....Pages 256-261
The λ-Calculus....Pages 262-268
While Programs....Pages 269-273
Beyond Undecidability....Pages 274-281
Gödel’s Incompleteness Theorem....Pages 282-286
Proof of the Incompleteness Theorem....Pages 287-291
Gödel’s Proof....Pages 292-298
Front Matter....Pages 299-299
Homework 1....Pages 301-301
Homework 2....Pages 302-302
Homework 3....Pages 303-303
Homework 4....Pages 304-305
Homework 5....Pages 306-306
Homework 6....Pages 307-307
Homework 7....Pages 308-308
Homework 8....Pages 309-309
Homework 9....Pages 310-310
Homework 10....Pages 311-311
Front Matter....Pages 299-299
Homework 11....Pages 312-312
Homework 12....Pages 313-313
Finite Automata and Regular Sets....Pages 315-332
Pushdown Automata and Context-Free Languages....Pages 333-339
Turing Machines and Effective Computability....Pages 340-350
Hints for Selected Miscellaneous Exercises....Pages 351-356
Solutions to Selected Miscellaneous Exercises....Pages 357-371
Back Matter....Pages 373-400
