Languages and Machines: An Introduction to the Theory of Computer Science (2nd Edition) [Hardcover]

Thomas A. Sudkamp (Author)

Book Description

Publication Date: November 4, 1996 | ISBN-10: 0201821362 | ISBN-13: 978-0201821369 | Edition: 2

Languages and Machines, which is intended for computer scientists in the theoretical foundations of their subject, gives a mathematically sound presentation of the theory of computing at the junior and senior level. Topics covered include the theory of formal languages and automata, computability, computational complexity, and deterministic parsing of context-free languages. To make these topics accessible to the undergraduate, no special mathematical prerequisites are assumed. The author examines the languages of the Chomsky hierarchy, the grammars that generate them, and the finite automata that accept them. The development of abstract machines continues with the Church-Turing thesis and computability theory. Computational complexity and NP-completeness are introduced by analyzing the computations of Turing machines. Parsing with LL and LR grammars is included to emphasize language definition and to provide the groundwork for the study of compiler design. The second edition now includes new sections covering equivalence relations, Rice's Theorem, pumping lemma for context-free grammars, the DFA minimization algorithm, and over 150 new exercises and examples.

Editorial Reviews

Amazon.com Review

Languages and Machines is a user-friendly text that covers the key ideas of the theory of computation clearly and thoroughly. Examples and numerous diagrams, including diagrams that illustrate the principle of induction, aid in the understanding of the material. Relative to other books containing similar information, this text contains in-depth coverage of languages and parsing.

From the Back Cover

No special mathematical prerequisites are assumed; the theoretical concepts and associated mathematics are made accessible by a 'learn as you go' approach that develops an intuitive understanding of the concepts through numerous examples and illustrations. Languages & Machines examines the languages of the Chomsky hierarchy, the grammars that generate them, and the finite automata that accept them. Sections on the Church-Turing thesis and computability theory further examine the development of abstract machines. Computational complexity and NP-completeness are introduced by analyzing the computations of Turing machines. Parsing with LL and LR grammars is included to emphasize language definition and to provide the groundwork for the study of compiler design.

Features

• A winning writing style, Languages and Machines is becoming recognized as an instructor's boon
• Effective examples that convey challenging and complex theoretical concepts
• Numerous diagrams illustrating pictorially the underlying concepts
• Step-by-step, unhurried proofs
• A "learn as you go" approach that develops mathematical sophistication

Features New to this Edition:

• DFA minimization
• Rice's Theorem
• Increased coverage of computational complexity
• Additional examples throughout
• Over 150 additional exercises

** Instructor's materials are available from your sales rep. If you do not know your local sales representative, please call 1-800-552-2499 for assistance, or use the Addison Wesley Longman rep-locator at http://hepg.awl.com/rep-locator.

0201821362B04062001

See all Editorial Reviews

Product Details

• Hardcover: 569 pages
• Publisher: Addison Wesley; 2 edition (November 4, 1996)
• Language: English
• ISBN-10: 0201821362
• ISBN-13: 978-0201821369
• Product Dimensions: 9.5 x 6.6 x 1.1 inches
• Shipping Weight: 2 pounds
• Average Customer Review: 3.3 out of 5 stars  See all reviews (15 customer reviews)
• Amazon Best Sellers Rank: #626,938 in Books (See Top 100 in Books)

More About the Author

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

Customer Reviews

Most Helpful Customer Reviews

11 of 11 people found the following review helpful:

5.0 out of 5 stars Excellent Book, A Must have., December 21, 1999

By 

Pecos Bill (Redwood City, CA) - See all my reviews

This review is from: Languages and Machines: An Introduction to the Theory of Computer Science (2nd Edition) (Hardcover)

This is one of the better books that I read on languages and machines. This book is great for someone who is interested in parsing, compilers or pattern matching. The book covers a lot of theory on computation and is not for a beginner. I would recommend that one be well grounded in set theory, recursion and mathematical induction before attempting to read this book. I did not read all the chapters; I only read those that were relevant to my project and I had not seen before in other texts. The 1st chapter get you upto speed with a good review of set theory followed by a quick review of induction and recursion. The 2nd chapter gives an excellent introduction to strings, languages and regular expressions along with relations on regular expressions. Chapter 3 is where the rubber hits the road. It covers context-free and regular grammars. I feel this chapter covers the subjects very well. Chapter 4 gives a good description of parsing and methods of parsing. Chapter 6 covers Finite Automata. This chapter describes deterministic finite state machines, nondeterministic finite state matchines and nondeterministic finite state matchines with lambda transitions. The presentation of the subject in this chapter was excellent. Chapter 7 presents Regular Languages and Sets. This chapter gives a good presentation of how to put together different types of machines from different languages and build languages from machines. I found it best not to read the chapters in orders, instead I read them in the following order which helped to understand the material better; 1,2,6,7,3,4,11,12

My only complaint: It would have helped if the author could have gave answers to some of the problems at the end of the chapters.

9 of 9 people found the following review helpful:

4.0 out of 5 stars A Good Book for a Tough Subject, February 14, 2006

By 

Joe Banks (New York, NY) - See all my reviews

This review is from: Languages and Machines: An Introduction to the Theory of Computer Science (3rd Edition) (Paperback)

Abstract language theory is hard, but Languages and Machines does a very good job of explaining the subject step by step. The topics are covered extremely thoroughly and with just the right amount of rigor. As for those who claim it's not exciting enough, you can't get blood out of a stone. Only the most dedicated computer scientist and mathematicians will find this topic interesting. Even so, this book does a superb job of tying theory to application (e.g., the machines one can use language theory to build) for even the most obscure concepts (like the Greibach Normal Form).

That being said, there are a few problems. First, the author's claim that this is a book for undergrads is not credible (except perhaps at MIT or CalTech). Even my graduate students have to read sections multiple times to "get it". Second, the author needs to provide solutions to selected problems at the back of the textbook. Most theory books do this, but not this one. This is a major weakness, especially given the difficulty of the material. Lastly, Sudkamp's proofs are extremely dry and very difficult to follow. He should take a cue from Sipser's "Intro to the Theory of Computation" book (which is generally too abstract for most students) and introduce "proof ideas" to give the big picture for important proofs.

6 of 6 people found the following review helpful:

4.0 out of 5 stars Taught by the author!, September 20, 2004

By 

Prithviraj Sharan "All's well that ends well" (Cambridge, MA) - See all my reviews
(REAL NAME)   

This review is from: Languages and Machines: An Introduction to the Theory of Computer Science (2nd Edition) (Hardcover)

Hey,
I was fortunate enough to learn this course from the author of the book. The book by itself might seem tough. The fault lies in the fact that subject matter is not altogether too simple to understand without someone teaching it to you!

With the help of the instructor, we did learn a lot about formal languages, finite automaton, regular grammer, etc.

The key to understanding this material (and using this book effectively) is solving as many problems as possible, preferably in a group setting so that solutions can be discussed.
Note: For most problems, there exists multiple solutions, and the approach is what needs to be learned and discussed.

Recommended, with some reservations...Good luck!