Automata, Computability and Complexity: Theory and Applications, 1st edition

Published by Pearson (August 8, 2018) © 2019

  • Elaine A. Rich
Products list
$79.95 AUD
Instant access

Access details

  • Instant access once purchased
  • Fulfilled by VitalSource

Title overview

For upper level courses on Automata.

Combining classic theory with unique applications, this crisp narrative is supported by abundant examples and clarifies key concepts by introducing important uses of techniques in real systems. Broad-ranging coverage allows instructors to easily customise course material to fit their unique requirements.

Table of contents

  • PART I: INTRODUCTION
  • 1 Why Study Automata Theory?
  • 2 Review of Mathematical Concepts
  • 3 Languages and Strings
  • 4 The Big Picture: A Language Hierarchy
  • 5 Computation
  • PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES
  • 6 Finite State Machines
  • 7 Regular Expressions
  • 8 Regular Grammars
    • 9 Regular and Nonregular Languages
  • 10 Algorithms and Decision Procedures for Regular Languages 
  • 11 Summary and References
  • PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA
  • 12 Context-Free Grammar
  • 13 Pushdown Automata
  • 14 Context-Free and Non-context Free Languages
  • 15 Algorithms and Decision Procedures for Context-Free Languages
  • 17 Summary and References
  • PART IV: TURING MACHINES AND UNDECIDABILITY
  • 18 Turing Machine
  • 19 The Church-Turing
  • 20 The Unsolvability of the Halting Problem
  • 21 Decidable and Semidecidable Languages
  • 22 Decidability and Undecidability Proofs
  • 23 Undecidable Languages That Do Not Ask Questions about Turing Machines
  • APPENDIX C: HISTORY, PUZZLES, AND POEMS
  • REFERENCES
  • INDEX
  • Appendices for Automata, Computability and Complexity: Theory and Applications:
  • Math Background
  • Working with Logical Formulas
  • Finite State Machines and Regular Languages
  • Context-Free Languages and PDAs
  • Turing Machines and Undecidability
  • Complexity
  • Programming Languages and Compilers
  • Tools for Programming, Databases and Software Engineering
  • Networks
  • Security
  • Computational Biology
  • Natural Language Processing
  • Artificial Intelligence and Computational Reasoning
  • Art & Entertainment: Music & Games
  • Using Regular Expressions
  • Using Finite State Machines and Transducers
  • Using Grammars

Need help?Get in touch