Page Tools:
  • print-friendly version

Introducing the Theory of Computation

Author(s): Wayne Goddard, Clemson University
Details:
  • ISBN-13: 9780763741259
  • ISBN-10:0763741256
  • Hardcover    228 pages      © 2009
Price: International Sales $158.95 US List
Add to Cart Request a Review Copy

Overview

Introducing the Theory of Computation is the ideal text for any undergraduate, introductory course on formal languages, automata, and computability.  The author provides a concise, yet complete introduction to the important models of finite automata, grammars, and Turing machines, as well as undecidability and the basics of complexity theory.  Numerous problems, varying in level of difficulty, round out each chapter and allow students to test themselves on key topics. Answers to selected exercises are included as an appendix and a complete instructor’s solutions manual is available on the text’s web site.

 

View Errata 

ShowKey Features

Provides a concise introduction to core topics taught in a single semester Theory of Computation or Automata Theory course.

Incorporates an engaging, student-friendly writing style and moves through material at a pace appropriate for undergraduate students.

A wide range of problems, varying in level of difficulty, allows students to test themselves on key material covered in the given chapter.

Back to top

ShowTable of Contents

Part 1:  Regular Languages

1.  Finite Automata
2.  Regular Expressions
3.  Nondeterminism
4.  Properties of Regular Languages
5.  Applications of Finite Automata

Part II:  Context-Free Languages

6.  Context-Free Grammars
7.  Pushdown Automata
8.  Grammars and Equivalencies
9.  Properties of Context-free Languages
10. Deterministic Parsing

Part III:  Turing Machines

11.  Turing Machines
12.  Variations of Turning Machines
13.  Decidable Problems and Recursive Languages

Part IV:  Undecidability

14.  Diagonalization and the Halting Problem
15.  More Undecidable Problems
16.  Recursive Functions

Part V:  Complexity Theory

17.  Time Complexity
18.  Space Complexity
19.  NP-Completeness


Back to top

ShowAbout the Author(s)

Wayne Goddard-Clemson University

Wayne Goddard is currently as Associate Professor in the School of Computing at Clemson University having previously taught at the Universities of KwaZulu-Natal and Pennsylvania.  His research interests are graph theory, algorithms, networks and combinatorics.  He received his PhDs from the University of KwaZulu-Natal and the Massachusetts Institute of Technology.  He has published over 100 journal and conference papers in many areas of graph theory as well as in graph algorithms, self-stabilizing algorithms, game-playing and ad hoc networks, and is co-author of a textbook on Research Methodology.

Back to top

ShowAppropriate Courses

Ideal for an undergraduate course in the Theory of Computation offered within the Computer Science or Computer Engineering Departments.

Back to top

ShowSamples & Additional Resources

ShowResources

    • show overview$38.95 Add to Cart

      JFLAP Activities for Formal Languages and Automata

      ISBN-13: 9780763772024

      This supplement contains material intended for students taking a first course in formal languages and automata theory and are using JFLAP in their work. It includes material that will help you to get started with JFLAP, gives hints on how to use it, and suggests exercises that show the power and convenience of JFLAP.

Back to top