Computer Science

My Instructor Resource Center : Log in or request access

Theory of Computing: A Gentle Introduction
Efim Kinber, Sacred Heart University
Carl Smith, University of Maryland

ISBN-10: 0130279617
ISBN-13: 9780130279613

Publisher: Prentice Hall
Copyright: 2001
Format: Paper; 207 pp
Published: 06/13/2000
Status: Instock

Net price: $92.25 (What's this?)

Request a printed exam copy

Email this page to a colleague
Prepare for the First Day of Class
Learn about customization options

Appropriate for upper division undergraduate and graduate level courses in Computer Science Theory, Theory of Computation, and Automata and Formal Language Theory.

This book focuses on fundamental issues of computation. The readers can master the content and gain lasting perspective from which to understand computers by carefully worked out examples, illustrations, and algorithmic proofs. It is especially appropriate for one-term courses.

“Lead by example” approach.
- Fundamental theorems are arrived at as generalizations of examples. Ex.___

Fundamental concepts behind computation are taught.
- Explains pattern matching, parsing, and helps to identify unsolvable problems. Ex.___

Hundreds of exercises marked according to the level of difficulty.
- Provides students ample opportunity to apply concepts. Ex.___

Hundreds of illustrations.
- Enhance understanding. Ex.___

Only algorithmic proofs are given in the text—Other proof details are left to exercises.
- Allows readers to calibrate the mathematical depth they want to pursue. Ex.___

(NOTE: Each chapter concludes with Exercises.)

1. Introduction.

Why Study the Theory of Computing? What Is Computation? The Contents of This Book. Mathematical Preliminaries.

2. Finite Automata.

Deterministic Finite Automata. Nondeterministic Finite Automata. Determinism versus Nondeterminism. Regular Expressions. Nonregular Languages. Algorithms for Finite Automata. The State Minimization Problem.

3. Context Free Languages.

Context-Free Grammars. Parsing. Pushdown Automata. Languages and Automata. Closure Properties. Languages That Are Not Context-Free. Chomsky Normal Form. Determinism.

4. Turing Machines.

Definition of a Turing Machine. Computations by Turing Machines. Extensions of Turing Machines. Nondeterministic Turing Machines. Turing Enumerable Languages.

5. Undecidability.

The Church-Turing Thesis. Universal Turing Machines. The Halting Problem. Undecidable Problems.

6. Computational Complexity.

The Definition and the Class P. The Class N P. N P-Completeness.

References.

List of Symbols.

Index.

Automata / Theory of Computation (Computer Science)

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.