The Strangest Book on the Theory of Computation

Based on the description of the book in the World Scientific Press catalogue, I asked my university library to order a book entitled Automata Theory by Matthew Simon. I did so because it seemed to cover many topics not available elsewhere. I now regret my decision, although looking at the book did provide some amusement value. It is weird.

The first thing that a reader notices is each chapter begins with lengthy quotations about the history of slavery. No, I am not kidding. Chapter 1, for example, begins as follows:


TABLE OF MIXTURES

TO BECOME WHITE

White and Negro produces mulatto
Half white, half black

White and mulatto produces quadroon
Three-quarters white and one-quarter Negro...


etc. This strange choice is explained by the author as follows: "While this book focuses upon language, a reminder of the relationship between language, social being, responsibility, and historical context will start each chapter."

The typesetting and notation are really awful. For example, the author uses the capital letter "X" to represent ×, the cross product symbol. Terms are used without being defined: for example, "semi-automata" is used on page 7 but has not been defined. Some material is simply repeated; for example, both pages 9 and 11 contain a definition of semigroups (which are sometimes written "semi-groups"). The author frequently uses notation and abbreviations that are unique to him, such as "NDFSA" for what everyone else calls "NFA", etc.

Most of the book consists of pages and pages and pages of examples, with little explanation of what the examples are intended to illustrate. When theorems are stated, they often miss the point. For example, the pumping lemma for regular languages is stated as follows: "If an FSA has n+1 states and accepts a string ω where ω = a₀ a₁ ... a_n+1, thus |ω| = n+2, then the FSA accepts an infinite number of strings." But this is not the pumping lemma, which is a statement about languages, not automata.

This is, without a doubt, the strangest book I have every read on the theory of computation. I honestly don't know how this book ever got published.

There is also an interesting positive review of the book on Amazon:


Automata Theory by Matthew Simon is an unusually welcome book. The many examples shown include subjects not often covered, such as: the Chomsky-Schutzenberger Theorem, Kuroda Normal Forms, Ginsberg-Griebach Theorem, Simple Pushdown Automata, Syntactic Pattern Recognition, and Shape Grammers. The use of a consistent and standard notation throughout the book is also welcome, as many different subjects are discussed. The focus of the first chapter is upon Semigroups and Automata Theory(including wreath products), from a more elementary, less abstract, less mathematical viewpoint than that found in the dozen or so books covering this subject. Thus examples from automata theory are emphasized. While departures from the notation of Clifford and Preston do take place, the notation is as close as one can come to being standard, as no standard notation currently exists. Each chapter starts with a commentary or quotes relating to subjects that arise in socially oriented linguistics and automata theory. Such commentary is often omitted in books covering automata theory but is of interest to people studying Anthropological Linguistics, General (historical)Linguistics, Philosophical Linguistics, and other academic areas dealing with linguistics, but often neglected by the engineering, Computer Science and Mathematics communities.


I leave it up to the reader to try to figure out who might have written this review.