John C. Martin (1)

Indeholder "Preface", "Introduction", "Part I. Mathematical Notation and Techniques", "1. Basic Mathematical Objects", " 1.1 Sets", " 1.2 Functions", " 1.3 Logical Statements", " 1.4 Proofs", " 1.5 Relations", " 1.6 Languages", " Exercises", "2. Mathematical Induction and Recursive Definitions", " 2.1 The Principle of Mathematical Induction", " 2.2 The Strong Principle of Mathematical Induction", " 2.3 Recursive Definitions", " Exercises", "Part II. Regular Languages and Finite Automata", "3. Regular Expressions and Regular Languages", " 3.1 Definitions: Regular Expressions and the Corresponding Languages", " 3.2 Examples and Applications", " Exercises", "4. Finite Automata", " 4.1 The Memory Required to Recognize a Language", " 4.2 Definitions and Representations", " 4.3 Extending the Notation: The Function δ*", " 4.4 Distinguishing One String from Another", " 4.5 Unions, Intersections, and Complements of Regular Languages", " Exercises", "5. Nondeterminism", " 5.1 Nondeterministic Finite Automata", " 5.2 Nondeterministic Finite Automata with Λ-Transitions ", " 5.3 The Equivalence of FAs, NFAs and NFA-Λs", " 5.4 Algorithms and Examples", " Exercises", "6. Kleene's Theorem", " 6.1 To Each Regular Expression There Corresponds a Finite Automaton", " 6.2 To Each Finite Automaton There Corresponds a Regular Expression", " Exercises", "7. Minimal Finite Automata", " 7.1 A Minimum-State FA for a Regular Language", " 7.2 Minimizing the Number of States in an FA", " 7.3 A More Efficient Algorithm for Marking Pairs", " 7.4 The Uniqueness of the Minimum-State FA", " Exercises", "8. Regular and Nonregular Languages", " 8.1 A Criterion for Regularity", " 8.2 The Pumping Lemma: Another Way to Prove a Language Nonregular", " 8.3 Decision Problems and Decision Algorithms", " 8.4 Regular Languages and Programming Languages; Finite Automata and Computers", " Exercises", "Part III. Context-Free Languages and Pushdown Automata", "9. Context-Free Languages", " 9.1 Definitions and Introduction", " 9.2 Examples: Natural Languages, Programming Languages, Algebraic Expressions, and Others", " 9.3 Unions, Concatenations, and *'s of CFLs", " 9.4 Regular Languages and Regular Grammars", " Exercises", "10. Derivation Trees and Ambiguity", " 10.1 Definitions and Examples", " 10.2 An Unambiguous CFG for Algebraic Expressions", " Exercises", "11. Simplified Forms and Normal Forms", " 11.1 Eliminating Λ-Productions from a CDF", " 11.2 Eliminating Unit Productions from a CDF", " 11.3 Eliminating Useless Variables from a CDF", " 11.4 Chomsky Normal Form", " Exercises", "12. Pushdown Automata", " 12.1 Introduction by Way of an Example", " 12.2 Definitions", " 12.3 More Examples", " 12.4 Deterministic PDAs", " 12.5 The Two Types of Acceptance Are Equivalent", " Exercises", "13. The Equivalence of CFGs and PDAs", " 13.1 For Any CFG There Is a PDA", " 13.2 For Any PDA There Is a CFG", " Exercises", "14. Parsing", " 14.1 Top-Down Parsing", " 14.2 Recursive Decent", " 14.3 Bottom-Up Parsing", " Exercises", "15. CFLs and Non-CFLs", " 15.1 The Pumping Lemma and Examples", " 15.2 Intersections and Complements", " 15.3 Decision Problems for CFLs", " Exercises", "Part IV. Turing Machines, Their Languages, and Computation", "16. Turing Machines", " 16.1 Models of Computation", " 16.2 Definitions: TMs as Language Acceptors", " 16.3 Combining Turing Machines", " 16.4 Computing a Function with a TM", " Exercises", "17. Variations of Turing Machines", " 17.1 TMs with Doubly-Infinite Tapes", " 17.2 TMs with More Than One Tape", " 17.3 Nondeterministic TMs", " 17.4 Universal Turing Machines", " Exercises", "18. Recursively Enumerable Languages", " 18.1 Recursively Enumerable and Recursive", " 18.2 Enumerating a Language", " 18.3 Not All Languages are Recursively Enumerable", " 18.4 Examples", " Exercises", "19. More General Grammars", " 19.1 Unrestricted Grammars", " 19.2 Grammars and Turing Machines", " 19.3 Context-Sensitive Grammars", " 19.4 Linear-Bounded Automata and the Chomsky Hierarchy", " Exercises", "20. Unsolvable Decision Problems", " 20.1 The Halting Problem", " 10.2 Other Unsolvable Problems Relating to TMs", " 20.3 Post's Correspondence Problem", " 20.4 Applications to Context-Free Languages", " Exercises", "21. Computablility: Primitive Recursive Functions", " 21.1 Computable Functions", " 21.2 Primitive Recursive Functions", " 21.3 More Examples", " 21.4 Primitive Recursive Predicates", " 21.5 Some Bounded Operations", " Exercises", "22. Computablility: μ-Recursive Functions", " 22.1 A Computable Total Function That Is Not Primitive Recursive", " 22.2 Unbounded Minimalization and μ-Recursive Functions", " 22.3 Gödel Numbering", " 22.4 All Computable Functions Are μ-Recursive", " 22.5 Nonnumeric Functions", " Exercises", "Part V. Introduction to Computational Complexity", "23. Tractable and Intractable Problems", " 23.1 Growth Rate of Functions", " 23.2 The Time Complexity of a Turing Machine", " 23.3 Tractable Decision Problems: The Class !", " 23.4 Nondeterminism and the Class ;!", " 23.5 NP-Completeness", " Exercises", "24. Some NP-Complete Problems", " 24.1 NP-Completeness of the Satisfiability Problem", " 24.2 Other NP-Complete Problems", " Exercises", "References", "Bibliography", "Index".

Ok introduktion til automater, turing-maskiner, beregnelighed og alt det der. Minder meget om pensum på andet år i datalogi i 1980.… (lisätietoja)