Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Introduction to computer theory
Cohen D., John Wiley & Sons, Inc., New York, NY, 1986. Type: Book (9789780471802716)
Date Reviewed: Feb 1 1987

At the time of this writing, there are well over a dozen books covering the basic results in an area which is broadly described by such key words as “Automata Theory,” “Formal Languages,” and “Theory of Computation.” All of these “text” books vary in their choice of topics and depth of coverage, but almost all of them are written at a reasonably sophisticated (first year graduate) level. The book under review is an exception to this trend. It devotes over 800 pages to the topics that are covered normally in 200 or so pages.

This book is divided into three parts. Part 1, Automata Theory, covers (in nearly 230 pages) most of the standard topics: languages and regular expressions, finite automata and their representation, concept of acceptance, regular languages, nondeterminism and its ramification, automata with output, basic properties of languages accepted by finite automata, and pumping theorems. Part 2 covers (in nearly 300 pages) context-free grammars, normal forms, pushdown automata and their relation to context-free languages, pumping theorems, deterministic context-free languages and pausing, and (non)closure properties. The last part covers (in 250 pages) most of the standard material on Turing machines. Chapter 1, on Background, provides a good historical perspective. The last chapter, Computers, illustrates, through many examples, the relation between these formal models and the more realistic computers. There are numerous problems given at the end of each chapter. The coverage is self-contained but there are virtually no citations to the literature.

The presentation is very leisurely and emphasizes the basic principles. The intuition behind every proof is clearly brought out, and almost all the ideas are illustrated with copious examples. While there is no general consensus as to the level at which a course on this array of topics should be introduced in a computer science curriculum, this book raises the hope that such a course may even be taught at the junior year. This book is indeed a very welcome addition to the literature.

Reviewer:  S. Lakshmivarahan Review #: CR110827
Bookmark and Share
  Featured Reviewer  
 
General (F.0 )
 
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
Theory of computation: formal languages, automata, and complexity
Brookshear J., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1989. Type: Book (9789780805301434)
Jan 1 1990
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