Automata, computability and complexity : theory and applications / Elaine Rich.

By: Rich, ElaineMaterial type: TextTextPublication details: New Delhi : Pearson Prentice Hall, c2008Description: xx, 1099 p. : ill. ; 25 cmISBN: 9788131788226 (pbk)Subject(s): Machine theory | Computable functions | Computational complexity | Electronic data processingDDC classification: 511.3
Contents:
PART I: INTRODUCTION 1. Why Study Automata Theory? 2. Languages and Strings 3. The Big Picture: A Language Hierarchy 4. Computation PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES 5. Finite State Machines 6. Regular Expressions 7. Regular Grammars 8. Regular and Nonregular Languages 9. Algorithms and Decision Procedures for Regular Languages 10. Summary and References PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA 11. Context-Free Grammars 12. Pushdown Automata 13. Context-Free and Noncontext-Free Languages 14. Algorithms and Decision Procedures for Context-Free Languages 15. Context-Free Parsing 16. Summary and References PART IV: TURING MACHINES AND UNDECIDABILITY 17. Turing Machines 18. The Church-Turing Thesis 19. The Unsolvability of the Halting Problem 20. Decidable and Semidecidable Languages 21. Decidability and Undecidability Proofs 22. Undecidable Languages That Do Not Ask Questions about Turing Machines 23. Unrestricted Grammars 24. The Chomsky Hierarchy and Beyond 25. Computable Functions 26. Summary and References Part V: Complexity 27. Introduction to the Analysis of Complexity 28. Time Complexity Classes 29. Space Complexity Classes 30. Practical Solutions for Hard Problems 31. Summary and References Appendices A: Review of Mathematical Background: Logic, Sets, Relations, Functions, and Proof Techniques B: The Theory: Working with Logical Formulas C: The Theory: Finite State Machines and Regular Languages D: The Theory: Context-Free Languages and PDAs E: The Theory: Turing Machines and Undecidability F: The Theory: Complexity Appendices G-Q: Applications G: Applications: Programming Languages and Compilers H: Applications: Tools for Programming, database and Software Engineering I: Applications: Networks J: Applications: Security K: Applications: Computational Biology L: Applications: Natural Language Processing M: Applications: Artificial Intelligence and Computational Reasoning N: Applications: Art and Environment: Music and Games O: Applications: Using Regular Expressions P: Applications: Using Finite State Machines and Transducers Q: Applications: Using Grammars
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Call number Status Date due Barcode Item holds
Books Books Namal Library
Mathematics 		511.3 RIC-A 2008 2916 (Browse shelf (Opens below)) Available 0002916
Total holds: 0

Includes bibliographical references and index.

PART I: INTRODUCTION 1. Why Study Automata Theory? 2. Languages and Strings 3. The Big Picture: A Language Hierarchy 4. Computation PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES 5. Finite State Machines 6. Regular Expressions 7. Regular Grammars 8. Regular and Nonregular Languages 9. Algorithms and Decision Procedures for Regular Languages 10. Summary and References PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA 11. Context-Free Grammars 12. Pushdown Automata 13. Context-Free and Noncontext-Free Languages 14. Algorithms and Decision Procedures for Context-Free Languages 15. Context-Free Parsing 16. Summary and References PART IV: TURING MACHINES AND UNDECIDABILITY 17. Turing Machines 18. The Church-Turing Thesis 19. The Unsolvability of the Halting Problem 20. Decidable and Semidecidable Languages 21. Decidability and Undecidability Proofs 22. Undecidable Languages That Do Not Ask Questions about Turing Machines 23. Unrestricted Grammars 24. The Chomsky Hierarchy and Beyond 25. Computable Functions 26. Summary and References Part V: Complexity 27. Introduction to the Analysis of Complexity 28. Time Complexity Classes 29. Space Complexity Classes 30. Practical Solutions for Hard Problems 31. Summary and References Appendices A: Review of Mathematical Background: Logic, Sets, Relations, Functions, and Proof Techniques B: The Theory: Working with Logical Formulas C: The Theory: Finite State Machines and Regular Languages D: The Theory: Context-Free Languages and PDAs E: The Theory: Turing Machines and Undecidability F: The Theory: Complexity Appendices G-Q: Applications G: Applications: Programming Languages and Compilers H: Applications: Tools for Programming, database and Software Engineering I: Applications: Networks J: Applications: Security K: Applications: Computational Biology L: Applications: Natural Language Processing M: Applications: Artificial Intelligence and Computational Reasoning N: Applications: Art and Environment: Music and Games O: Applications: Using Regular Expressions P: Applications: Using Finite State Machines and Transducers Q: Applications: Using Grammars

There are no comments on this title.

to post a comment.