Languages and Machines: An Introduction to the Theory of Computer Science

by Thomas A. Sudkamp and Sudkamp, Thomas A. Sudkamp, Thomas A.

Book Overview

The third edition of Languages and Machines: An Introduction to the Theory of Computer Science provides readers with a mathematically sound presentation of the theory of computer science. The... This description may be from another edition of this product.

• Format: Hardcover
• Language: English
• ISBN: 0201821362
• ISBN13: 9780201821369
• Release Date: November 1996
• Publisher: Addison Wesley Publishing Company
• Length: 500 Pages
• Weight: 2.00 lbs.
• Dimensions: 1.1" x 6.6" x 9.5"

Customer Reviews

A Good Book for a Tough Subject

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.

Taught by the author!

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!

Excellent Book, A Must have.

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,12My only complaint: It would have helped if the author could have gave answers to some of the problems at the end of the chapters.

A good introduction, bent towards formal languages

I have a mathematical background and wished to acquaint myself with the basics of theoretical computer science. This book didn't disappoint me.The book stresses formal languages and parsing, and is therefore best suited for persons interested in creating languages, compiler technology and parsing. However, it covers also Turing machines, computability and complexity issues, among others, and is therefore reasonably comprehensive.Exercises range from easy to moderate, and many of them are stimulating. Another reviewer complained about the lack of drill exercises (see below). I can understand the anguish of students; some of the exercises, as well as parts of the text, may be difficult if one doesn't have much experience in formal reasoning and abstract problem solving. However, all exercises I have taken a look at are solvable with the knowledge provided in the text, and are therefore suitable for readers with at least a fair mathematical background.My main complaint is the small number of applications. In chapter 3, there is a nice example: the arithmetic expressions of Pascal; in chapter 15, good examples of NP-complete problems. However, these are exceptions. In my opinion the text would greatly benefit from e.g. end-of-chapter exercises related to programming mini-languages which could be defined on the spot. Also examples of finite state machines (copier machines, services in a mobile phone etc.) would add flesh to exercises.All in all, this is a good entry point to theoretical computer science for a person trained in mathematics or a related field, but may partly be too challenging to a first-year student.

A good readable survey of CS theory

Although I'm not a maven of CS theory, Sudkamp's book makes the subject comprehensible and approachable. It spans the range of the subject and does a good job of preparing the reader for further readings in automata, computability, and decidability.