Introduction to Languages and the Theory of Computation

by John C. Martin

Paperback, 1991

Status

Available

Call number

511.3

Library's review

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.
… (more)

Publication

McGraw-Hill Education (ISE Editions) (1991), Paperback, 480 pages

Description

This text introduces undergraduates to the theory of computation, with an emphasis on formal languages, automata and abstract models of computation and computability. Features include an introduction to computational complexity and NP-completeness, numerous examples, and inclusion of Ogden's Lemma.

Language

Original language

English

Physical description

543 p.; 23.5 cm

ISBN

0071008519 / 9780071008518

Local notes

Omslag: John Hite
Omslaget viser en simpel automat med tre tilstande
Indskannet omslag - N650U - 150 dpi
Page: 0.7322 seconds