Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Theory of computation: formal languages, automata, and complexity
Brookshear J., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1989. Type: Book (9789780805301434)
Date Reviewed: Jan 1 1990

As the discipline of computer science matures, demand to introduce its basic theoretical foundations at the undergraduate level is growing. In this book, the author has succeeded in providing a delightful introduction to this area. The book is pedagogically sound and inviting. The basic ideas are motivated through and abstracted from practical problems. The style is informal, yet the book contains adequate theory suitable for junior- or senior-level courses.

After the introductory chapter, which defines the basic notions and concepts from discrete mathematics, the remainder of the book may be divided into three parts. Part 1, consisting of chapters 1, 2, and 3, introduces the basic concepts of finite automata, pushdown automata, Turing machines, the classes of languages accepted by these machines, and relationships between language classes. This part is replete with examples drawn from compiler design. Part 2 further analyzes Turing machines from the point of view of computability theory. This part, consisting of chapter 4, provides a solid introduction to recursive function theory and Turing computability. Part 3 introduces the notion of resource-bounded computations, in particular the P-class, the NP-class, and NP-completeness. Five short appendices and over 150 exercise problems extend the main development.

Reviewer:  S. Lakshmivarahan Review #: CR113381
Bookmark and Share
  Featured Reviewer  
 
General (F.0 )
 
 
Automata (F.1.1 ... )
 
 
Bounded-Action Devices (F.1.1 ... )
 
 
Classes Defined By Grammars Or Automata (F.4.3 ... )
 
 
Computability Theory (F.1.1 ... )
 
 
Recursive Function Theory (F.4.1 ... )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "General": Date
Introduction to computer theory (revised ed.)
Cohen D., John Wiley & Sons, Inc., New York, NY, 1991. Type: Book (9780471510109)
Feb 1 1993
Introduction to computer theory
Cohen D., John Wiley & Sons, Inc., New York, NY, 1986. Type: Book (9789780471802716)
Feb 1 1987
Computability, complexity, and languages (2nd ed.)
Davis M., Sigal R., Weyuker E., Academic Press Prof., Inc., San Diego, CA, 1994. Type: Book (9780122063824)
Dec 1 1995
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy