Automata Theory with Modern Applications

James Anderson

Publisher Cambridge University Press
ISBN 9780521848879
RRP £55
Reviewed by Simon Clarke CEng FBCS CITP
Score 7 out of 10

Automata Theory This newly published book is a mathematical textbook for tertiary-level students wishing to study the theory behind automata, grammars and Turing machines.

The style of the book is wholly theoretical, and does not discuss implementations or practical aspects. The book contains many self-learning exercises. The solutions are not included, but are available from the publishers.

The book starts with a basic introduction to set theory and builds on this discuss relations, functions and semigroups. It builds on this to describe automata and the standard Mealy and Moore finite-state machines. Included in these chapters are descriptions of retracts and semiretracts.

It would have been good to have seen a description of the newer developments in finite-state machines, such as David Harel’s Hierarchical State Machine. This is widely in UML. It has characteristics of both the Mealy and Moore machines, and so a discussion of the theory behind this would have been apt.

The later chapters describe formal grammars and Turing machines. The book concludes with a short chapter outlining the application of formal language theory to molecular biology and the new science of DNA computing.

The general style of the book is fairly terse and concise with few examples or asides to break up the text. This makes it dense reading. There is no attempt to discuss implementations, coding or practical aspects.

This should suit the target audience of students of mathematics or computer science. Programmers or software engineers will not find it has direct relevance to them, other than to explain the theory.

At 260 pages, this is a quite short introduction to a large topic. The book competes against some larger, well-established standard texts. 

I recommend this book for those who need a concise introduction to automata theory, but do not need extensive applications, examples or implementation details.

Further information: Cambridge University Press