Author: Alan P. Parkes
Publisher:Springer, 2008
ISBN: 978-1848001206
Aimed at: Undergraduates in Computer Science
Rating: 4
Pros: Covers academic topics with plenty of introductory help
Cons: Quickly ramps up
Reviewed by: Mike James

First and foremost it is important to realise that this book isn’t about computer hardware nor is it about programming languages or assembler. It's about the theory of formal languages, grammar and abstract machines such as the Turing machine. It’s the sort of material covered in any good computer science degree.

What is special about this particular text book is that it attempts to introduce the very mathematical ideas of formal grammars and symbolic manipulation in a way that is easy to understand even if you don’t know much modern maths.

For example in the first chapter it introduces the formal mathematical notation necessary to work up to production rule grammars and the Chomsky hierarchy by spelling out what each means in everyday English. This is a very good approach but if continued at this level would make the book thousands of pages long and eventually it has to switch to using just the notation and developments on the notation without spoon feeding the reader.

What this means is that at some point the mathematically naive reader is going to stop and wonder what some expression means. This is also made harder by the fact that there is no glossary of symbols and no “crib” sheet to let you check what each part of the expression might mean.

As a result, despite the very gentle start the reader will eventually have to put some work into making the transition from non-maths speaking to maths speaking. The gentle start does however make it more likely that the attempt will be made and might encourage some readers who think of themselves as maths haters to think that it is at least possible.

A bigger problem however is that when we finally reach the Chomsky hierarchy it is presented as a table, in a fairly formal style, with very little attempt at giving the reader any feeling for what sort of language characteristics the hierarchy is controlling. It doesn’t give any insight into why we bother to build such a set of restrictions. This omission is made up for in later chapters but why wait so long to motivate such comparatively simple ideas?

The rest of the book deals with the standard ideas encountered on a course on the theory of computation working its way through finite state machines to the Turing machine and the idea of universal computer. Finally the book rounds off with an overview of computability, solvability and the halting problem and a brief excursion into dimensions of computation and the “big O” notation.

By the end of the book the reader should be able to appreciate the big questions such as P=NP? and will be either ready to move on to something more advanced or will be better educated in the very basics of computational theory.

If you are looking for a textbook to base a course on, or need a refresher especially if your maths is a little rusty, this is a good choice but it isn’t suitable as a general non-technical introduction.I hope that the next edition adds material to make up for these problems because it's a good book that could be excellent.