Buy Used
+ £2.80 UK delivery
Used: Good | Details
Sold by momox co uk
Condition: Used: Good
Comment: Please allow 1-2 weeks for delivery. For DVDs please check region code before ordering.
Have one to sell?
Flip to back Flip to front
Listen Playing... Paused   You're listening to a sample of the Audible audio edition.
Learn more
See this image

Elements of the Theory of Computation Paperback – May 1988

See all 5 formats and editions Hide other formats and editions
Amazon Price New from Used from
"Please retry"
--This text refers to an out of print or unavailable edition of this title.

Product details

  • Paperback: 466 pages
  • Publisher: Pearson Education (US); New edition edition (May 1988)
  • Language: English
  • ISBN-10: 0132734265
  • ISBN-13: 978-0132734264
  • Product Dimensions: 22.8 x 14.8 x 2.6 cm
  • Average Customer Review: 3.0 out of 5 stars  See all reviews (2 customer reviews)
  • Amazon Bestsellers Rank: 3,252,925 in Books (See Top 100 in Books)

More About the Authors

Discover books, learn about writers, and more.

Customer Reviews

3.0 out of 5 stars
5 star
4 star
3 star
2 star
1 star
See both customer reviews
Share your thoughts with other customers

Most Helpful Customer Reviews

8 of 9 people found the following review helpful By Amazon Customer on 24 Sept. 2003
Format: Hardcover
I'm an University student at Portugal (University of Algarve), and my Infinitesimal Math 3 course was replaced with the Theoretical Foundations of Computer Science course.
One of the advised books was this "Elements of the Theory of Computation" by H. R. Lewis e C. H. Papadimitriou, which isn't an easy book to the ones that don't like "abstractions". This book is about Math/Computer Science, with an high level of formalism, due to all the theorems and proofs, so it implies that you have some mathematical background and interest. This isn't a Programming book.
Some people say that this is an advanced book, not be given to undergraduate students, but the fact is that this is a course lectured in the 2nd year of my Computer Science - Teaching Branch degree, here in my University.
This book covers an introduction to Discrete Mathematics (sets, relations, strings, ...), Finite Automata ( regular expressions and languages ), Context-free Languages, Turing Machines, Uncomputability and the Halting Problem (undecidable problems), Computational Complexity and NP-Completeness.
One of the major problems of this book is the lack of suficient solved examples, precious to self learners like myself. Most authors forget this crucial aspect. I'm one of the persons that prefers to learn by example.
Other good alternatives to this book (they cover most of the same topics) are:
- "Automata and Formal Language" by Dean Kelley.
- "Introduction to the Theory of Computation" by M. Sipser
- "Introduction to Automata Theory, Languages and Computation" by J. E. Hopcroft, R. Motwani e J. D. Ullman
Elements of the Theory of Computation is a good book, but not a basic one. And it's target audience is very restricted. Surely not a "for dummies" like type.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
0 of 1 people found the following review helpful By Tea Tenhunen on 30 Oct. 2013
Format: Hardcover Verified Purchase
Bought the book from Amazon and it turned out to be paperback instead of hardcover. Couldn't return it as it was needed right away but felt pretty cheated, the book was expensive. I paid for hardcover and got paperback instead. The contents of the book itself is what was expected, no problem there.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again

Most Helpful Customer Reviews on (beta) 35 reviews
33 of 36 people found the following review helpful
An Amazing Book on tough topic 20 Nov. 2001
By Sean Francisco Smith - Published on
Format: Hardcover
This was one of my favorite textbooks from college. In fact, I still have it on my shelf. It is a fantastic textbook, attemtping to introduce the Theoretical Foundations of Computer Science, in essence the science. In covering this, it moves into topics such as Finite Automata, Parsing, and Turing Machines.
I feel the negative reviews are due to some confusion. This is not an algorithms book, or a programming book, or an "intro to AI" book. It's a Math textbook. It's language is one of theorems and proofs, and this would be hard going for someone not comfortable with a college-level abstract mathematics background.
For those of you who have such a background, this book covers a topic where mathematics can become elegant. A physics major friend of mine fell in love with it, and he had no interest in Comp Sci!!
For it's topic, a similar book would be Feynman's lecture notes on Physics. Both those volumes and this book were attempt to bring the highest levels of theory within the field to the undergraduate audience. Both succeed.
16 of 16 people found the following review helpful
You'll love it or hate it. 20 Sept. 2003
By Jason T - Published on
Format: Hardcover
I discuss the first edition- I havent read the updated version. People have strong opinions about this classic book. Many students have it forced upon them for a class and they absolutely despise it. But a small number of people like me loved it, in fact its still one of my favorite textbooks. I first learned automata and computation theory here (which explains some of my fondness for the book), and it seemed kind of dull and strange until about halfway through- at which point I realized it's all very cool and I subsequently poured over the entire book several times. To get through it you need to enjoy mathematics and careful, rigorous definitions and proofs- rather than viewing these things as pointless obscurantism or pedantic arrogance. Engineering students tend to find the book dense, boring, and too difficult. Some people are intimidated by the sheer volume of special notation used. But if you're inclined towards mathematics or theoretical work you'll appreciate the extra rigor and precision (compared to most computation theory books). There are a few rough spots in it (I admit the development of the Herbrand expansion theorem in the last chapter is a mess, and the coverage of parsing theory isn't great), and some of the terminology and approaches are a little nonstandard, but overall a great book that will give you the foundation to begin studying computational complexity theory, recursive function theory, or mathematical logic. Note that the second edition has removed the chapters on logic, and I've heard its watered down. If you want something a little harder and more pure-math oriented, try Martin Davis's Computability and Unsolvability.
8 of 9 people found the following review helpful
A good textbook 24 April 2005
By Jill Malter - Published on
Format: Hardcover
I taught a couple of classes from the first edition of this textbook, and my students did fairly well. On the whole, they were able to understand the material and solve the homework problems. I certainly wouldn't mind teaching a class on this subject from the second edition as well, which I feel is a mild improvement over the first one.

The chapter on finite automata is excellent. And the material on context-free languages is thorough and well written. So is the introduction to Turing machines.

Of course, the book then spends a fair amount of time on recursive function theory. That is exactly what I want it to do. And I think the chapter on unsolvability, starting with the Halting Problem, is excellent.

The style, especially of the first edition, is a little formal. But this is serious mathematical material, and I think it is not asking too much to require students to handle this subject in such a manner.
4 of 4 people found the following review helpful
First and foremost, a math book 20 April 2005
By Joshua Davies - Published on
Format: Hardcover Verified Purchase
I enjoyed this book because I enjoy formal mathematics. This is not an applications book, but a formal study of the mathematics that underly algorithmic design and analysis. I'm no math wizard, and I found this book readable (but I had to take it very slowly). The course for which I bought the book only covered chapters 1 - 4 and glossed over the final 3 chapters, but I intend to read the rest over the summer between semesters because it's so well and thoroughly written. This book is *dense*. I had to re-read everything three times before I absorbed it all, but ultimately I've understood everything I've read. The hardest parts to understand were the formal "proofs by induction" on the lengths of strings and sets - and, as any math student knows, you can gloss over the proofs on the first reading. A lot of the formal definitions (finite automata, pushdown automata, Turing machines, context-free grammars, etc.) baffled me on the first reading, but after reviewing the examples and working through a few problems, I could go back, re-read the formal definition and understand it.

My principal complaint with this book, and the only reason I gave this book a four-star review instead of five, is the same complaint I have with a lot of other textbooks - there are no answers for any of the problems (nor can I find a supplement or a study guide or any help anywhere). Given the nature of the problems themselves, it's impossible to verify your answers. This seems to be a trend in textbooks, and it's extremely frustrating. I plan to self-study the last half of the book in the next few months, but without a self-study guide, I'm pretty much out of luck if I can't solve a problem.
5 of 6 people found the following review helpful
A classic text on the theory of computation. 24 July 2003
By James Arvo - Published on
Format: Hardcover
Elements of the Theory of Computation, by Lewis and Papadimitriou, is something of a classic in the theory of computation. Of the many books I have used to teach the theory of computation, this is the one I have been most satisfied with. It covers all of the fundamental concepts one would expect in such a book (more on this below) but offers a bit more mathematical rigor than most other books I've seen on this topic. It also covers one topic that is rarely even mentioned in other textbooks: the composition of Turing machines.
The book begins with a brief introduction to the relevant discrete mathematics (such as set theory and cardinality) and proof techniques, then introduces the concepts of finite automata, regular expressions, and regular languages, describing their interrelationships. It proceeds to context-free languages, pushdown automata, parse trees, pumping lemmas, Turing machines, undecidability, computational complexity, and the theory of NP-completeness. (These are all standard topics.) Along the way, Lewis and Papadimitriou also introduce random access Turing machines and recursive functions, and do a nice job of explaining the halting problem and how this translates into undecidable problems involving grammars, various questions about Turing machines, and even two-dimensional tiling problems. All of these topics are covered with an appropriate mix of formalism and intuition.
Perhaps the feature I like best is the discussion of composing simple Turing machines to obtain more complex and interesting machines. The authors even introduce a convenient graphical notation for combining Turing machines and spell out specific rules for composition. While most authors are forced to immediately employ heuristics in reasoning about complex Turing machines (lest the notation become overwhelming), Lewis and Papadimitriou are able to keep the discussion more formal and structured by virtue of their Turing machine "schema". I believe this makes their arguments more rigorous and even easier to follow.
This is clearly one of the best books on the theory of computation. However, be aware that there have been very significant changes from the first edition, which was lengthier and more thorough. I confess that I actually prefer the first edition, as it contains nice sections on logic and predicate calculus (which have been removed from the 2nd edition), and is a bit more formal (albeit with some fairly awful notation). The 2nd edition is definitely crisper, with much cleaner notation; it is clearly more student-friendly, which was presumably the aim of the new edition.
If you wish to teach an introduction to theoretical computer science, or wish to learn it on your own, this would be a fine book to use. It's hard to go wrong with this classic.
Were these reviews helpful? Let us know