Customer Reviews

Introduction to Languages and the Theory of Computation

5 star:		(10)
4 star:		(1)
3 star:		(2)
2 star:		(0)
1 star:		(9)

 

 

Logic and linguistics interweave and become virtually indistinguishable through the unifying topic of computability. Any serious seeker of knowledge must be familiar with the underlying concepts of computation. Psychology, philosophy, computer science, the physical and metaphysical are all touched upon by this one subject.

The approach of this work is fairly standard. It begins with machines generating or recognizing languages of increasing inclusiveness and generality, and proceeds to further subject matter, computability and complexity. It opens with two introductory chapters covering the basics of set theory, inductive proofs, and linguistic concepts which will be utilized throughout the book. Each topic after this builds upon the previous ones systematically and gradually. Both mathematical/logical, and verbose prose descriptions are employed, to coax the reader through this intricate and immensely important subject.

One must be well grounded in reading mathematics. The introductory chapters will likely be insufficient for the neophyte, who may become frustrated as the material develops, even as gradual as this cumulation is. Rigorous proofs are provided, and the reader is expected to appreciate the underlying implications. One must exert some considerable personal effort to achieve this level.

This work stands at a middle ground in the subject, between the relatively informal approach of the excellent Sipser text, and the extremely thorough work by Hopcraft et al. It expects the reader to approach the subject with seriousness, yet provides gentler guidance through the more complex subtopics than other related works having this level of mathematical rigor.

I am a 39-year-old MBA student in an AACSB-accredited business school, with a C.S. degree from Purdue University. When I took "Theory of Languages and Computation" (hereafter: TOLAC) in my 20's, this text did not suit me at all.

Recently, however, I've been refreshing my CS-foundations by reading (CLR) "Intro. to Algorithms", my discrete math text, and others. Though I graduated having understood the broad conclusions of TOLAC (e.g., the equivalence of various languages and the abstract machines which recognize them, complexity classes, etc.), I never felt that I "knew" them deeply the way I prefer to know things.

I study and build compilers for a hobby; there are many practical issues to which the TOLAC lends itself. As I was gearing up for some hobby compiler projects, I decided to reacquaint myself with TOLAC. Though I still have my undergraduate Martin text, I recalled how I didn't connect well with it, so decided to peruse Amazon for suggested texts (with Sipser's work getting an impressive number of high marks, the likes of which I've not seen from a "CS book").

I was right on the verge of purchasing Sipser's book, with its glowing reviews, when I decided to lift my Martin text (1991-edition) from its tucked away position on the bookshelf. I was immediately pleased with its slim and concise presentation (having a wife and three kids can be a damper on my study time). As I started reading the first pages, I was struck with an elegance that I obviously had missed years before. Before I knew it, I had been reading for a few hours and was completely taken by the subject, including Martin's mathematical style.

I found myself asking, "Why did I so dislike then the book from which I am receiving so much pleasure now?" I think it had to do with my maturity and stage-of-life. In school, when taking TOLAC, I was more interested in "just writing code" (I had gotten my first C compiler on a Commodore-64 at the age of 12, so I loved programming). Whereas now, I am truly interested in the "science" aspect of "computer science." I find myself, almost twenty years later, really coming to an understanding of the difference between a "CS" degree and a "CPT" (computer programming technology) degree. (The CPT degree is a fine degree; so please don't misinterpret what I'm saying.) But, having grown up coding in my bedroom, and having my entire professional career in IT, I see now the tremendous value of the _rigor_ and _abstraction_ of a CS degree. To be sure, there were dimwits in my CS program who couldn't do anything practical; these were the types who had never programmed anything, and making linked-lists with C was to them a Gordian knot. But I must respectfully say, there have been many situations where I was able to bring an insight from Turing machines, algorithms, TOLAC, data structures, complexity classes, et al., from the computer science world, into a practical situation that had others (good "CPT people") stumped.

Now, I by no means wish to slander the CPT credential, nor the skills of the fine people who possess it. But I realize, upon writing this review, that the rigor and abstraction of the CS degree prepares the mind for things which I honestly don't think the CPT person can appreciate. It's like the many levels of calculus I took which the CPT degree did not require. Have I taken an integral or a derivative since school? No. But I have an insight into practical IT situations, programming and otherwise, which often seem to elude my CPT comrades. Now I may have the good fortune of being a "bedroom programmer" combined with CS-training; but I don't think I'd have the practical problem-solving skills without having suffered (yes, suffered) what I did via the CS degree.

As for Martin vs Sipser: I have not read Sipser, but I take from the 200+ glowing reviews that his text takes a complex subject and makes it digestible to the young mind; and that is certainly praiseworthy. So I encourage the contemporary CS student to study Sipser's book. However, I also recommend you work (and suffer) through Martin's text. Yes, both texts, regardless of which is required for your particular class.

The analogy that I'm about to employ is way oversimplified and may be deemed an insult by some, so please do not take it that way; please see it in the spirit with which I intend: I'm sure that a young college student could peruse the cartoon guide to calculus rather than working out hundreds of painful problems. The cartoon-guide-reader will likely come away with the "big ideas" of what calculus is about, and probably even have a sense for when it is necessary. But there is something lost in the student by doing so. In similar "spirit" (but an imperfect analogy), it's like using using Java vs C when introducing the development of elementary data structures and algorithms. In "freeing" the student from having to manage all those pointers, it may be thought that the student is able to get at the concepts without being ensnared in useless details. But again, the student is being cheated by not permitting him/her to _suffer_ through the details. I've encountered many good "Java people" (or to be even more abstract, many good -people) who simply glaze over when any real level of abstraction is needed in a situation. [To clarify: Sipser's text is by no means a cartoon-guide to TOLAC; Java is by no means a bad language.] Perhaps this is more of an indictment of the state of education in America than anything else, but we cheat ourselves and our students when we put rubbing padding on all the corners at the playground.

So, to end this rambling, I will say: coming back to my CS books after many years has given me a deeper appreciation of why the word "science" is appended. CPT languages and techniques come and go, but the principles and foundation of computer science remain. Frankly, a skilled craftsman must be accomplished in both disciplines: an ivory-tower CS person who cannot implement is as much to be criticized as a CPT person who cannot analyze deeply or abstractly (e.g., being completely dependent on his Visual Basic class library).

As for the Martin text: if you read the whole thing, chapter by chapter, then you'll notice that he gradually builds up the rigor. He holds your hand a lot in the beginning stages. (I think one problem I had years ago was that I lazily skipped the foundation chapters, which made later notation and some concepts more troublesome.) My edition (1991)(which, by the way, you can get used on Amazon) is slim, concise, with nicely laid out pages. In this age of phonebook-sized unedited get-it-to-market rubbish, it is refreshing to hold such a handsome text.

The Martin text has not changed. I disliked it "then," but I suffered through it then and I believe it's made me a stronger practitioner; I am loving it "now." Having the maturity and patience for the text, I find it to be quite a gem. (Much like "Moby Dick." Going through it in high school was a torturous bore; I am simply captivated by it now.)

Respectfully,

Jason Massey
Indianapolis

i am currently enrolled in a course for which this is the required text and have found this book to be all but totally useless. this is the first semester the text is being used and the professor has already decided to switch textbooks for the next semester. i am placing an order for michael sipser's textbook in hopes that i can still salvage my grade in this course. in summary, this book is a waste of paper, both literary- and money-wise.

i hope this insight is useful to other undergrad students who are in the same situation.

I read this book during my preparation for a comprehensive exam, which includes materials about theory of computation. I was bad at theory all the time, but reading this book removes all my confusions. It looks like lots of math at first glance, but all the theorems explained clearly after the declarations. This book is also very helpful to understand the fundamental theory for programming languages. I recommend this book for all new graduate students of computer science.

I've had the privilege of taking Prof. Martin's two-semester course from this text here at NDSU, and it has been quite enjoyable. The text provides a solid description and set of proofs for the more mathematically-minded students (such as myself). I think that the problem that many other reviewers seem to have faced is that their instructors fall short in their ability to teach this subject. Coupled with a good instructor (such as Prof. Martin) who gives very accessible and intuitive proofs in lecture (possibly by sacrificing rigor in favor of understanding), this text allows a student to have a solid understanding of the topic from a mathematically rigorous point of view.

One word summarized this book--horrible. This book sucks to the max! It's confusing and hard to understand. If it is your desire to be confused and be confusing then read this book. ANY other book is infinitely better than this one such as: "Introduction to the Theory of Computation" by Michael Sipser (really good AND got good reviews from other people here; see for yourself; shows I'm not alone) or "Languages and Machines" by Thomas Sudkamp (pretty good) or "Computable Languages and Abstract Machines" (excellent) by Alan Parkes or "The Language of Machines" by Robert Floyd and Richard Beigel. Trust me. I have examined ALL five of these books and John Martin's is THE worst. Don't waste your money on this one. Take it from an average person that likes to read (obviously) and strives to learn but not from someone who can't explain things well!

As far as basic ideas of automata goes, this book will do. It's not phenomenal, and it's not awful. It is merely sufficient. The main problem is that it lacks elegance in a number of places. In many places, it feels sloppy. Definitions are almost arbitrary, and often lack rigor. Techniques are long, tedious, and not very interesting. (This is nowhere more evident that the finite automaton -> regular expression conversion from Ch. 4, which has a really neat solution that this book does NOT give.) Yet, despite all this, it conveys the important ideas nevertheless.

As far as developing skills for more advanced concepts of theory of computation, things don't look so good. This book's approach can be described as attempting, by sheer force, to make automata problems fit into rather vanilla proof techniques that readers will probably have already learned. The result is likely to do little more than convince readers that the subject is hard.

The information presented in this book is compact and difficult to understand. I am using this book in my undergraduate class right now and I have to re-read sections over a few times before I start to understand the material. I'd recommend getting another text if you are unfortunate enough to use such a book in your class. I'd recommend getting Micheal Sipser's book on Automata theory. The point of a text is to be clear and concise to the reader, but Martin's book falls short on both.

During the course this book has been anything but helpful. The introductory part is a laugh as it takes for given you as a reader is very deep into mathematical lingo and proofs. Indeed the poofs are some of the worst written, many of them using statements as "Clearly it is..." and "It is now easy to see...", well, no, it isn't easy and mostly seems like a shortcut from the author to excuse himself from actual explanations.

Even worse is the examples where solutions reference something form an excercise, here's a hint to Mr Martin, students don't solve all the extremly many excercises unless asked to, so saying something will be clear after a certain excercise doesn't work, how will we ever know if we're right or wrong?

The educational value is very low due to the authors way of writing, never really getting the point across and always assuming the reader knows exactly what's going on. This is certainly not the way to teach people rather complex things. All in all anyone should look elsewhere to have a chance.

First of all, the word "Introduction" in the title is misleading. It is assumed you already understand set theory because the "review" at the beginning is skimpy at best. You'll need other references to back this book up. Secondly, there are no answers to any of the exercise questions. Combining this with the skimpy coverage at the beginning, the student is left to his/her own devices for arriving at the correct answers. Answers to some of the exercise problems would have been extremely helpful for a student studying after hours--especially with a subject like this.