Floyd and Beigel introduce formal languages and computability using a unique paradigm of machines and programs. A machine consists of devices such as control sets, input devices, and Turing tapes, each having a canonical set of operations. A program for a machine consists of device initializers, instructions (that is, tuples with operations for each device), and terminators.

These tools permit the authors to introduce different machine models, nondeterminism, computations, blocking, program simulations, and program standardizations in the first three chapters. Finite machines have only a control set and possibly input and output devices; pushdown automata add a stack; counter machines add a counter; and Turing machines add a Turing tape. For example, a Turing machine is defined as [control, input, output, Turing tape], whereas Hopcroft and Ullman [1] define it as the more complicated tuple . Some standard automata terms are never introduced: automata are called recognizers, acceptors, and transducers; finite automata are called finite machines; and pushdown automata are called stack machines. Determinism, computations, and blocking computations depend on instructions and therefore programs, not machines. Program simulation, which is treated explicitly, is used to show equivalences between programs on different machine models. Using standardizations independent of the machine model, loop instructions can be removed, blocking states can be removed, and programs can be factored so only one non-control device operates during each instruction. These program transformations simplify proofs such as showing that deterministic context-free languages are closed under complementation. Using this paradigm of machines and programs, the authors present finite automata, regular languages, context-free languages, pushdown automata, counter machines, Turing machines, computability, recursion theory, and an introduction to the complexity classes P and NP.

Aimed at third-year undergraduates, the textbook easily serves a one-semester automata and computability course (though the course name would have to change, since the term “automata” never appears in the book). A 12-week course could cover one chapter per week, with extra weeks for finite machines and Turing machines. The writing mixes mathematical rigor with numerous examples and illustrations. Proofs occasionally merge into the text, sometimes confusing the reader and sometimes clarifying the material. Remarkably few mistakes appear in this first edition, demonstrating the authors’ concern for a clear explanation of the material.

The nonstandard paradigm prevents this book from serving as a reference on formal languages, automata theory, and computability. Standard terms such as automata, pushdown automata, and sentential form are not defined. Representations such as for a context-free grammar do not appear. The book contains no bibliography or references. The limited number of exercises help undergraduate students learn the material but fail to challenge beginning graduate students. Instructors considering using the textbook must be willing to use the book’s paradigm, possibly supplementing the material with standard terms and definitions.