Models of Computation and Formal Languages [Hardcover]

R. Gregory Taylor (Author)

Book Description

Publication Date: October 2, 1997 | ISBN-10: 019510983X | ISBN-13: 978-0195109832

Models of Computation and Formal Languages presents a comprehensive and rigorous treatment of the theory of computability. The text takes a novel approach focusing on computational models and is the first book of its kind to feature companion software. Deus Ex Machina, developed by Nicolae Savoiu, comprises software simulations of the various computational models considered and incorporates numerous examples in a user-friendly format.
Part I of the text introduces several universal models including Turing machines, Markov algorithms, and register machines. Complexity theory is integrated gradually, starting in Chapter 1. The vector machine model of parallel computation is covered thoroughly both in text and software. Part II develops the Chomsky hierarchy of formal languages and provides both a grammar-theoretic and an automata-theoretic characterization of each language family. Applications to programming languages round out an in-depth theoretical discussion, making this an ideal text for students approaching this subject for the first time. Ancillary sections of several chapters relate classical computability theory to the philosophy of mind, cognitive science, and theoretical linguistics.
Ideal for Theory of Computability and Theory of Algorithms courses at the advanced undergraduate or beginning graduate level, Models of Computation and Formal Languages is one of the only texts that... � � Features accompanying software available on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp/ Adopts an integrated approach to complexity theory
� Offers a solutions manual containing full solutions to several hundred exercises. Most of these solutions are available to students on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp � Features examples relating the theory of computation to the probable programming experience of an undergraduate computer science major

Editorial Reviews

Review

"A comprehensive, advanced introductory textbook on the theory of computation that can be used on an undergraduate level as well as graduate. The solutions manual and software are welcome additions."--Philip Demp, Rutgers University

Advance praise: "Taylor's work joins a small group of comprehensive yet rigorous, sweeping yet approachable, computer science textbooks. That by itself is a feast, but the dessert is Savoiu's intuitive software that supports almost every chapter by providing working examples, a homework bench, and a model-programming environment." --Benjamin Wells, University of San Francisco

About the Author

R. Gregory Taylor holds degrees from the University of Michigan, New York University, and Columbia University. He is currently chair of the Department of Computer Science at Jersey City State College.

Product Details

• Hardcover: 688 pages
• Publisher: Oxford University Press, USA (October 2, 1997)
• Language: English
• ISBN-10: 019510983X
• ISBN-13: 978-0195109832
• Product Dimensions: 9.5 x 7.7 x 1.5 inches
• Shipping Weight: 3.2 pounds
• Average Customer Review: 4.0 out of 5 stars  See all reviews (6 customer reviews)
• Amazon Best Sellers Rank: #491,583 in Books (See Top 100 in Books)
  • #91 in Books > Computers & Technology > Computer Science > Artificial Intelligence > Theory of Computing

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

13 of 13 people found the following review helpful:

5.0 out of 5 stars Unusually readable textbook on the theory of computing, January 7, 2000

By 

Nancy Tinkham (New Jersey) - See all my reviews
(REAL NAME)   

This review is from: Models of Computation and Formal Languages (Hardcover)

The theory of computing can be a difficult subject to master, because of the densely symbolic notation and the mathematical complexity of the concepts. When I was a graduate student preparing for the theory portion of my exams, I remember being dismayed at the choice of textbooks that was available at the time: most simply threw a collection of Greek letters and subscripts at the reader, with little attempt to provide simply-worded explanations that would give the reader an intuition for the concepts.

Now that I am teaching the theory of computing, I want to provide my students with the best textbook I can find.

Two years ago, I was delighted to find R. Gregory Taylor's new book, "Models of Computation and Formal Languages". This is by far one of the most readable theory textbooks I have encountered. One of the features that caught my eye when I first examined the book was that many of the complicated symbolic expressions are accompanied by little explanatory text boxes with arrows that point to a symbol in the expression and explain the symbol that the arrow points to. I do this in class when I am lecturing -- I point to various symbols and explain where they came from, sometimes jotting down notes on the board alongside the symbols -- but this is the first time I have seen this technique in a textbook.

The writing style of the book is also fairly friendly and informal, without compromising mathematical precision.

The coverage of Turing-equivalent computing models is broader than in most introductory theory books; Taylor includes chapters not only on Turing Machines, but also on Recursive Function Theory, Markov Algorithms, Register Machines, Post Systems, and a model of parallel computation. Additionally, most chapters end with a proof that the model presented in that chapter is computationally equivalent to Turing Machines; thus, by the time the Church-Turing thesis is introduced in chapter 8, the reader is well prepared to entertain the claim that all of these models are capturing the same basic notion of an "algorithm".

I highly recommend this book to readers who want a readable introduction to computability theory.

2 of 3 people found the following review helpful:

5.0 out of 5 stars Difficult subject, yes, but very readable book, January 17, 2000

By 

Anthony Mendoza (Portland, Oregon) - See all my reviews

This review is from: Models of Computation and Formal Languages (Hardcover)

I was a bit taken aback by the "reader from United States" who gave this book only one star. The subject is difficult so the book is difficult. The book is as readable as possible given the subject matter. As Albert E. once said, "As simple as possible, but no simpler". This book strikes that balance.

0 of 2 people found the following review helpful:

3.0 out of 5 stars Not as good as the coment already posted, February 16, 2003

By A Customer

This review is from: Models of Computation and Formal Languages (Hardcover)

Basically, this book is not as good as for teaching use. I don't like the style of how the author state or arrange the topic. A lot confusion. But for those who have stronger math ground, it may be a not bad reference. The most point where I dispointed is the example or the solution of the excise is too abstract. The detailed induction, proof, explaination is especially importantant for beginner.So use this book as a reference.Don't choose as text book. Hard to follow!!!!