Introduction to Languages and the Theory of Computation [Hardcover]

John Martin (Author)

Book Description

ISBN-10: 0072322004 | ISBN-13: 978-0072322002 | Publication Date: August 6, 2002 | Edition: 3rd

Introduction to Languages and the Theory of Computation is an introduction to the theory of computation that emphasizes formal languages, automata and abstract models of computation, and computability; it also includes an introduction to computational complexity and NP-completeness. Through the study of these topics, students encounter profound computational questions and are introduced to topics that will have an ongoing impact in computer science. Once students have seen some of the many diverse technologies contributing to computer science, they can also begin to appreciate the field as a coherent discipline. A distinctive feature of this text is its gentle and gradual introduction of the necessary mathematical tools in the context in which they are used. Martin takes advantage of the clarity and precision of mathematical language but also provides discussion and examples that make the language intelligible to those just learning to read and speak it. The material is designed to be accessible to students who do not have a strong background in discrete mathematics, but it is also appropriate for students who have had some exposure to discrete math but whose skills in this area need to be consolidated and sharpened.

Editorial Reviews

Amazon.com Review

Even those with little mathematical background will be able to understand this user-friendly book, which focuses on formal languages and models of computation. (The author devotes an entire chapter to induction and recursive definitions.) Introduction to Languages and the Theory of Computation weaves numerous examples and highly readable discussions of the key ideas--and how they fit into the larger picture--in between rigorous proofs of the theorems. --This text refers to an out of print or unavailable edition of this title.

Product Details

• Hardcover: 560 pages
• Publisher: McGraw-Hill Science/Engineering/Math; 3rd edition (August 6, 2002)
• Language: English
• ISBN-10: 0072322004
• ISBN-13: 978-0072322002
• Product Dimensions: 9.3 x 7.5 x 1.1 inches
• Shipping Weight: 2.2 pounds (View shipping rates and policies)
• Average Customer Review: 3.1 out of 5 stars  See all reviews (22 customer reviews)
• Amazon Best Sellers Rank: #796,411 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

13 of 15 people found the following review helpful:

5.0 out of 5 stars Rigorous and cumulative approach to computation, December 17, 1999

By 

Rahman (CA, USA) - See all my reviews

This review is from: Introduction To Languages and The Theory of Computation (Hardcover)

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.

6 of 7 people found the following review helpful:

5.0 out of 5 stars Disliked it then, Love it now, March 20, 2010

By 

Jason Massey (Indianapolis, Indiana USA) - See all my reviews
(REAL NAME)   

This review is from: Introduction to Languages and the Theory of Computation (Hardcover)

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

6 of 7 people found the following review helpful:

1.0 out of 5 stars do NOT buy this book as an introductory text!, November 22, 2000

By 

digital shadow (the server closet) - See all my reviews

This review is from: Introduction To Languages and The Theory of Computation (Hardcover)

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.