HomeGroupsTalkMoreZeitgeist
Search Site
This site uses cookies to deliver our services, improve performance, for analytics, and (if not signed in) for advertising. By using LibraryThing you acknowledge that you have read and understand our Terms of Service and Privacy Policy. Your use of the site and services is subject to these policies and terms.
Hide this

Results from Google Books

Click on a thumbnail to go to Google Books.

Loading...

Introduction to Languages and the Theory of Computation

by John C. Martin

MembersReviewsPopularityAverage ratingConversations
1001213,338 (3.45)None
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.
None
Loading...

Sign up for LibraryThing to find out whether you'll like this book.

No current Talk conversations about this book.

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. ( )
  bnielsen | Oct 13, 2013 |
no reviews | add a review
You must log in to edit Common Knowledge data.
For more help see the Common Knowledge help page.
Canonical title
Original title
Alternative titles
Original publication date
People/Characters
Important places
Important events
Related movies
Awards and honors
Epigraph
Dedication
First words
Quotations
Last words
Disambiguation notice
Publisher's editors
Blurbers
Original language
Canonical DDC/MDS

References to this work on external resources.

Wikipedia in English (1)

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.

No library descriptions found.

Book description
Haiku summary

Quick Links

Popular covers

Rating

Average: (3.45)
0.5
1
1.5
2 1
2.5 1
3 3
3.5
4 4
4.5
5 1

Is this you?

Become a LibraryThing Author.

 

About | Contact | Privacy/Terms | Help/FAQs | Blog | Store | APIs | TinyCat | Legacy Libraries | Early Reviewers | Common Knowledge | 160,282,320 books! | Top bar: Always visible