The Language of Machines: An Introduction to Computability and Formal Languages

The distinctive feature of this text is that wherever possible, it develops the subject from the standpoint of [theoretic] machines rather than purely from algebraic constructions. This almost always makes the concepts more intuitive, just as the Turing machine is often considered more intuitive than studying first order logics and their models. I highly recommend this book, but in general the reader should be aware that the subject is so rich and complex that no single book can suffice. Books on automata, mathematical logic, and modern/general/universal algebra can come in handy. It looks as if this book is already out of print; it is surprising that the publisher did not give this book an extended life given that Floyd is one of the authors and that this was his only book. This is Floyd of Floyd-Warshall shortest paths, Floyd-Steinberg dithering, Floyd-Hoare style verification, and though not named after him, he more or less can be considered the founder of parsing and backtracking algorithms.

LOM is or ought to be a classic. For my money, it's the "Dragon Book" for undergrad/graduate teaching of a first course in automata theory.This book was used as the textbook in the automata theory course that I took post-baccalaureate. It is probably the book most responsible for my decision to go to grad school. I was working almost full time during the term I took this class, and I remember getting up early just so I would have a chance to read the optional material, since evenings were for the required parts.And yes, it was my first exposure to the subject; indeed to all of theoretical computer science, since I'd not yet taken an algorithms, discrete math, or programming languages course. Contrary to the frustration expressed in some other 1-star reviews (many from Chicago -- same class? same person?), I found the material clearly and systematically presented. The one change I think would benefit the book is a slightly more terse formalism, although what's given seems designed to aid the intuition of the learner.Yes the exercises were hard. But most of the problems are also very beautiful, and the insight I gained by doing them fully justified the effort. Even several years past the last of my grad course work, my memory of the course that used this book remains one of the highpoints of my education. As a basic reference work, I think LOM compares well to many other related texts. Sipser's more terse style is probably quite usable in the hands of a lecturer who can fill in the missing pieces, but I suspect it would be much harder to use on your own. In addition to the standard chapters on automata, formal languages, and computability (all extensive), there is a chapter each on recursion theory and intractability. Chapter 0, giving mathematical preliminaries, is *60 pages* long, and is the material I used to learn the prerequisite discrete mathematics.

This is the most hardcore CS book I have ever set eyes upon. Topics covered in this book are postgraduate-level discussions of the type that allow us to make decisions about the computability of the most difficult problems that computers solve. If you can gain a clear understanding of concepts in this book you should easily be paid in excess of 100,000 annually. Learn and apply the techniques in this book and you might be in posession of the kind of mind that wins a Nobel prize.

This is a clearly written introduction to theoretical aspects of computer science. The first six chapters are devoted to the Chomsky hierarchy followed by chapters on computability, recursion theory and complexity. An energetic student may also want to consult Sipser, Kiesler, Papadimitiou, Gruska and/or Savage.

Typically books of this nature are shrouded in cryptic and terse (albeit mathematically precise) theory. This book reworks the presentation in a more understandable way (e.g. non-determinism is presented early and used often; the term automata is dropped for the more descriptive term finite machine). I used this text last fall (fall '99) for an intro course on automata and formal languages and I plan on using it again.