| Description |
1 online resource (406 pages) |
| Contents |
UNDERGRADUATE TEXTS IN COMPUTER SCIENCE; Automata and Computability; Copyright; Preface; Contents; Lectures; Lecture 1 Course Roadmap and Historical Perspective; Lecture 2 Strings and Sets; Lecture 3 Finite Automata and Regular Sets; Lecture 4 More on Regular Sets; Lecture 5 Nondeterministic Finite Automata; Lecture 6 The Subset Construction; Lecture 7 Pattern Matching; Lecture 8 Pattern Matching and Regular Expressions; Lecture 9 Regular Expressions and Finite Automata; Supplementary Lecture A Kleene Algebra and Regular Expressions; Lecture 10 Homomorphisms |
|
Lecture 11 Limitations of Finite AutomataLecture 12 Using the Pumping Lemma; Lecture 13 DFA State Minimization; Lecture 14 A Minimization Algorithm; Lecture 15 Myhill-Nerode Relations; Lecture 16 The Myhill-Nerode Theorem; Supplementary Lecture B Collapsing Nondeterministic Automata; Supplementary Lecture C Automata on Terms; Supplementary Lecture D The Myhill-Nerode Theorem for Term Automata; Lecture 17 Two-Way Finite Automata; Lecture 18 2DFAs and Regular Sets; Lecture 19 Context-Free Grammars and Languages; Lecture 20 Balanced Parentheses; Lecture 21 Normal Forms |
|
Lecture 22 The Pumping Lemma for CFLsLecture 23 Pushdown Automata; Supplementary Lecture E Final State Versus Empty Stack; Lecture 24 PDAs and CFGs; Lecture 25 Simulating NPDAs by CFGs; Supplementary Lecture F Deterministic Pushdown Automata; Lecture 26 Parsing; Lecture 27 The Cocke-Kasami-Younger Algorithm; Supplementary Lecture G The Chomsky-Schützenberger Theorem; Supplementary Lecture H Parikh's Theorem; Lecture 28 Turing Machines and Effective Computability; Lecture 29 More on Turing Machines; Lecture 30 Equivalent Models; Lecture 31 Universal Machines and Diagonalization |
|
880-01 Miscellaneous Exercises Turing Machines and Effective ComputabilityHints for Selected Miscellaneous Exercises; Solutions to Selected Miscellaneous Exercises; References; Notation and Abbreviations; Index |
|
880-01/(S Lecture 32 Decidable and Undecidable ProblemsLecture 33 Reduction; Lecture 34 Rice's Theorem; Lecture 35 Undecidable Problems About CFLs; Lecture 36 Other Formalisms; Lecture 37 The λ-Calculus; Supplementary Lecture I While Programs; Supplementary Lecture J Beyond Undecidability; Lecture 38 Godel's Incompleteness Theorem; Lecture 39 Proof of the Incompleteness Theorem; Supplementary Lecture K Godel's Proof; Exercises; Miscellaneous Exercises Finite Automata and Regular Sets; Miscellaneous Exercises Pushdown Automata and Context-Free Languages |
| Notes |
Print version record |
| Subject |
Machine theory.
|
|
Computable functions.
|
|
Computable functions
|
|
Machine theory
|
| Form |
Electronic book
|
| Author |
Gries, David
|
|
Schneider, Fred B
|
| ISBN |
9781461218449 |
|
1461218446 |
|
