What do you think?
Rate this book
Essentials of Theoretical Computer Science
University of Kentucky Profesor Emeritus F.D. Lewis's text is divided into five major chapters named Computability, Unsolvability, Complexity, Automata, and Languages. Each of these in turn consists of several smaller sections.
- GenresComputer Science
ebook
39 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 of 1 review
April 22, 2012
Essentials of Theoretical Computer Science isn't your standard cs theory book. Almost every other theory book I've ever read, including the classic Sipser book, starts off with finite state machines, then builds up to pushdown automata, then covers turing machines, in a sort of "lets increase the power" manner. Once Turing Machines are covered, the books cover decidability and reducibility, and complexity.
Lewis's book almost completely flips this around, immediately jumping into Turing Machines, decidability, reducibility, and the difference between recursive and recursively enumerable sets. Afterwards, a more standard approach is taken, covering finite state automata, pushdown automata, and then linear-bounded automata. THEN complexity. Finally, the concept of a grammar is introduced, in the very last chapter.
At first, I was really skeptical of this ordering. It seemed completely backwards to me, but after reading through the book, I've completely changed my mind. This is the ideal order to present this material, and I now consider almost every other theory book to be fundamentally flawed.
Covering TMs first and discussing decidability in the first chapter provides an anchor point for every other discussion about other kinds of sets and automata. And saving grammars to the very end lets the reader focus us reducibility and closure properties of sets without muddying the waters with parsing or the Chomsky hierarchy.
In addition to the completely unorthodox and excellent ordering of the material, the book is extremely readable, written in a conversational, occasionally humorous tone. Proofs are simple and straightforward (as well as ample) and usually followed by a practical example as well to help solidify concepts. Despite the strangeness of the book, I highly recommend it for undergraduates and graduates studying CS Theory.
To make things even better, the entire book is completely free as an eBook from the author on his web site. If you have an interest in CS Theory, you owe it to yousrelf to read this book, which you simply can't beat for the price.
Lewis's book almost completely flips this around, immediately jumping into Turing Machines, decidability, reducibility, and the difference between recursive and recursively enumerable sets. Afterwards, a more standard approach is taken, covering finite state automata, pushdown automata, and then linear-bounded automata. THEN complexity. Finally, the concept of a grammar is introduced, in the very last chapter.
At first, I was really skeptical of this ordering. It seemed completely backwards to me, but after reading through the book, I've completely changed my mind. This is the ideal order to present this material, and I now consider almost every other theory book to be fundamentally flawed.
Covering TMs first and discussing decidability in the first chapter provides an anchor point for every other discussion about other kinds of sets and automata. And saving grammars to the very end lets the reader focus us reducibility and closure properties of sets without muddying the waters with parsing or the Chomsky hierarchy.
In addition to the completely unorthodox and excellent ordering of the material, the book is extremely readable, written in a conversational, occasionally humorous tone. Proofs are simple and straightforward (as well as ample) and usually followed by a practical example as well to help solidify concepts. Despite the strangeness of the book, I highly recommend it for undergraduates and graduates studying CS Theory.
To make things even better, the entire book is completely free as an eBook from the author on his web site. If you have an interest in CS Theory, you owe it to yousrelf to read this book, which you simply can't beat for the price.
Displaying 1 of 1 review